2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1 ... 7, 8, 9, 10, 11
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение02.09.2017, 21:21 
Заслуженный участник
Аватара пользователя


30/01/06
63897
Ага, спасибо.

То есть, для полного разгадывания надо в схемах ещё и указать, где чьи перчатки?

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение02.09.2017, 21:46 
Заслуженный участник


14/01/11
1636
Ну, я этого не требовал. Тем более, что ни одна из схем по сути не требует переодевания перчаток в процессе.

Вот, кстати, вспомнился ещё один неплохой сюжет по поводу обмена разумами, имевший место в мультсериале "Футурама". Там присутствует "мозгообменник", позволяющий обменивать разумами любых двух персонажей с ограничением: если два тела обменялись разумами, устройство больше не может выполнить между ними обмен.
В цитате ниже сформулирована любопытная математическая задача, возникающая в связи с этим.
Цитата:
К концу эпизода все устают от новых тел и хотят опять стать сами собой. К сожалению, из-за сбоя в работе мозгообменника возникает серьезная проблема: если два тела обменялись разумами, устройство больше не может выполнить между ними обмен. В итоге становится не совсем понятно, как вернуть разумы в свои тела.

Сценаристы включили в эпизод сбой в работе мозгообменника, чтобы сделать сюжет интереснее. Однако кому-то надо было найти способ решить эту проблему и обеспечить счастливый конец истории. Ответственность легла на Кена Килера, ведущего сценариста данного эпизода. Килер понимал, что единственный выход из создавшегося тупика — включить в сценарий новых персонажей, способных обеспечить косвенные пути, с помощью которых профессор и остальные герои могли бы вернуться в свои тела. Но вместо того чтобы заняться самим сценарием «Узника Бенды», Килер сфокусировался на более общей задаче: сколько новых людей необходимо включить в группу любого размера, чтобы распутать неразбериху, возникшую в результате обмена разумами?

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение02.09.2017, 23:44 
Заслуженный участник
Аватара пользователя


30/01/06
63897
Sender в сообщении #1244688 писал(а):
Тем более, что ни одна из схем по сути не требует переодевания перчаток в процессе.

Однако перчатки накладывают ограничения на схемы, и придают им больше логичности, как я понимаю.

Sender в сообщении #1244688 писал(а):
В цитате ниже сформулирована любопытная математическая задача, возникающая в связи с этим.

Задача недоформулирована. Как я понимаю, при некоторых уточнениях ответ может быть 0.

    (Оффтоп)

    Пусть в группе $ABCD$ совершены обмены $AB$ и $CD.$ Тогда достаточно совершить обмены $AC$ и $BD,$ а затем - $AD$ и $BC.$

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 00:16 
Заслуженный участник


14/01/11
1636
Munin в сообщении #1244706 писал(а):
Как я понимаю, при некоторых уточнениях ответ может быть 0.

Разумеется. Например, когда желаемая перестановка совпадает с исходной. :wink:
Вероятно, речь о минимальном количестве дополнительных участников, достаточном для распутывания любой наперёд заданной ситуации с обменами в группе из $n$ персонажей.

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 02:12 
Заслуженный участник
Аватара пользователя


30/01/06
63897
И даже здесь не уточнено, например, какие обмены внутри исходной группы запрещены, а какие нет.

    (Оффтоп)

    Всегда хватит $n$ дополнительных. Раскладываем исходную перестановку в произведение транспозиций. После этого, для каждой транспозиции - "достраиваем квадрат", такой как в предыдущем сообщении, над двумя исходными персонажами, и над соответствующими им дополнительными.

    Возможно, снизить эту оценку нельзя.

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 03:44 
Аватара пользователя


11/08/11
941
В случае, когда поменянные люди образуют цикл (то есть первый попал в тело второго, второй попал в тело третьего, ... , энный попал в тело первого) достаточно всего трех дополнительных людей. Для простоты берем самый худший для нас случай, когда все поменянные уже поменяны друг с другом, и можно менять их только с кем-то из дополнительных людей.

Назовем их, например, Мартин, Лютер и Кинг. На первом этапе пусть поработает один только Мартин, а Лютер и Кинг постоят в сторонке. Меняем Мартина сознанием с первым человеком. Мартина со вторым. Мартина с третьим. ... Мартина с энным. В итоге подготовительного этапа видим, что почти все люди уже оказались в своих телах, остались только Мартин и самый первый человек (назовем его, эмм, Вася), поменянные друг с другом. А эту задачу мы уже знаем как решить, и тут-то нам пригодятся Лютер с Кингом.

Отсюда закономерный вывод, что поскольку любую перестановку можно разбить на несколько циклов, то достаточно дополнительных людей в количестве, равном утроенному количеству циклов.

Можно ли обойтись еще меньшим количеством, пока соображаю.

-- 03.09.2017, 04:06 --

Потрясающе! Достаточно всего четырех дополнительных человек. Разобьем поменянных на циклические группы. Назовем этапом процедуру поочередного обмена сознаниями Мартина с членами некоторого цикла. После первого этапа имеем вернувшихся в свои тела членов первого цикла за исключением Васи Первого, поменянного телами с Мартином. Переходим к следующему этапу. Меняем Мартина телами с членами второго цикла. После этого этапа имеем вернувшихся в свои тела членов и первого, и второго циклов, за исключением Васи Первого и Васи Второго, причем: в теле Мартина теперь Вася Второй; в теле Васи Второго - Вася Первый; в теле Васи Первого сидит Мартин.

Повторяем этапы до тех пор, пока не исчерпаем все циклы. По итогам имеем, внезапно, Мартина и нумерованных Василиев, циклически поменянных сознаниями. Как разрешить проблему в случае одного цикла - смотрим предыдущий пост. Потребуется еще три человека, плюс Мартин равно четыре.

Итого: если поменянные люди образуют один цикл, то достаточно трех дополнительных помощников; если поменянные образуют циклы числом более одного, достаточно четырех помощников.

Как бы теперь доказать, что меньшим количеством не обойтись...

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 09:34 
Заслуженный участник


14/01/11
1636
Munin в сообщении #1244722 писал(а):
И даже здесь не уточнено, например, какие обмены внутри исходной группы запрещены, а какие нет.

Собственно, вот единственное ограничение:
Sender в сообщении #1244688 писал(а):
если два тела обменялись разумами, устройство больше не может выполнить между ними обмен

Какие трудности вызывает его формулировка? Впрочем, есть ещё одно условие: желательно, чтобы помощники в конце концов тоже вернулись в свои тела.

-- Вс сен 03, 2017 09:37:03 --

INGELRII, ваш результат можно ещё улучшить. :-)

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 09:45 


21/05/16
845
Аделаида
А это имеет какое-либо отношение к данетке?

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 10:17 
Заслуженный участник


14/01/11
1636
Можно заметить, что найдётся ситуация, когда меньше, чем двумя дополнительными обойтись нельзя. Пусть изначально у нас есть только двое: Вася и Петя, обменянные друг с другом.
Попробуем обойтись одним Лютером. Мы обмениваем его с Васей. А потом с Петей. (или наоборот). И всё, приехали.
А вот если у нас помимо Мартина есть Лютер, мы проводим следующую цепочку обменов:
М-В, Л-П, М-П ,Л-В, М-Л.

-- Вс сен 03, 2017 10:19:57 --

kotenok gav в сообщении #1244751 писал(а):
А это имеет какое-либо отношение к данетке?

Опосредованное. :-)

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 11:27 
Заслуженный участник
Аватара пользователя


30/01/06
63897
Sender в сообщении #1244748 писал(а):
Какие трудности вызывает его формулировка?

Неизвестно, сколько обменов уже происходило. То есть, в начальные условия должна входить не только перестановка, но и список совершённых (и тем самым запрещённых) обменов. Равные перестановки могут быть разным образом разложены на транспозиции.

-- 03.09.2017 11:33:15 --

Если запрещённые обмены не образуют полный граф, то возможно, в качестве перечисленных INGELRII четверых (Мартин-1, Мартин-2, Лютер-2, Кинг-2) можно использовать кого-то из исходной группы (особенно Лютер-2 и Кинг-2 подозрительны).

-- 03.09.2017 11:33:42 --

INGELRII
Изображение

 Профиль  
                  
 
 Re: Данетка по книгам - 4 (разгадана)
Сообщение03.09.2017, 13:25 
Заслуженный участник


14/01/11
1636
Munin в сообщении #1244768 писал(а):
Неизвестно, сколько обменов уже происходило.

А, это. Конкретная ситуация не задана, требуется найти максимум минимального достаточного числа помощников по всем возможным ситуациям с заданным числом участников.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 161 ]  На страницу Пред.  1 ... 7, 8, 9, 10, 11

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group