Данетка по книгам - 4 (разгадана)

[Munin]

Ага, спасибо.

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

[Sender]

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

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

Цитата:

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

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

[Munin]

Sender в сообщении #1244688 писал(а):

Тем более, что ни одна из схем по сути не требует переодевания перчаток в процессе.

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

Sender в сообщении #1244688 писал(а):

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

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

(Оффтоп)

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

[Sender]

Munin в сообщении #1244706 писал(а):

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

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

[Munin]

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

(Оффтоп)

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

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

[INGELRII]

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

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

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

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

-- 03.09.2017, 04:06 --

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

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

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

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

[Sender]

Munin в сообщении #1244722 писал(а):

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

Собственно, вот единственное ограничение:

Sender в сообщении #1244688 писал(а):

если два тела обменялись разумами, устройство больше не может выполнить между ними обмен

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

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

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

[kotenok gav]

А это имеет какое-либо отношение к данетке?

[Sender]

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

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

kotenok gav в сообщении #1244751 писал(а):

А это имеет какое-либо отношение к данетке?

Опосредованное.

[Munin]

Sender в сообщении #1244748 писал(а):

Какие трудности вызывает его формулировка?

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

-- 03.09.2017 11:33:15 --

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

-- 03.09.2017 11:33:42 --

INGELRII

[Sender]

Munin в сообщении #1244768 писал(а):

Неизвестно, сколько обменов уже происходило.

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