Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

94. 100 узников №3.б) (новогодняя версия)

В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем:

В одной из камер расставлены в ряд 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики — разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открывать и заглядывать в те ящики, которые хочет, но максимум он может открыть 50 ящиков из 100. Его задача в том, чтобы среди открытых им ящиков оказался тот, в котором лежит бумажка с его именем.

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

Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть время перед началом испытания, чтобы договориться о стратегии, которая позволит выиграть с максимальными шансами.

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

Найдите стратегию, которая позволит узникам гарантированно (со 100% вероятностью) успешно справиться с этим испытанием.
Прим. ред.
Аналогично задаче «100 узников №3.а) (ящики с именами)».
2013-01-01

Обсуждение


Задачи :: 100 узников №3.б) (новогодние ящики с именами)
↓↓ 0 ↑↑   eruditor.ru (92 / 199)   05 янв 2013 20:12   »»


Решение
Так же как и в 60 задаче представим эти ящики как множество циклических списков - если в ящике с именем "Миша" лежит записка "Миша", то ящик ссылается сам на себя (список "Миша"->"Миша"), если там лежит "Маша", а "Маша" ссылается на "Миша", то есть список "Миша"->"Маша"->"Миша" и т.д. Понятно, что если каждый заключенный начинает просмотр со свого ящика, то он должен дойти по списку до себя же не более чем за 50 шагов. Также понятно, что может существовать тольо один цикл длиной X > 50 ящиков (т.к. всего 100 ящиков и длина оствшихся циклов будет меньше или равна 100 - X). Теперь возьмём любой ящик из этого цикла, отсчитаем от него X/2 ящиков и поменяем в них бумажки - теперь у нас есть вместо большого цикла два маленьких, длиной X/2. Длина всех циклов < 50, значит все заключенные выживают.
↓↓ +4 ↑↑   PetrK (14 / 7)   21 янв 2013 17:27   «« #2 »»   Ответить


Это не решение. Это ответ.
Ответ без решения - совершенно не интересен.
↓↓ 0 ↑↑   eruditor (89 / 438)   12 фев 2013 15:41   «« #3 »»   Ответить


Это не ответ. Это решение.
Изложен план действий для заключенного и объяснено почему он сработает. Это называется решение. Всякие ненужные подробности типа как найти максимальный по длине цикл (прошли один цикл, переходим к первому непосещённому ящику) или почему списки циклические (показывается от противного или даже просто из принципа Дирихле) я опустил.
↓↓ 0 ↑↑   PetrK (14 / 7)   20 фев 2013 12:46   «« #4 »»   Ответить


Вдогонку
Ну а как потом действовать заключенным сказано в решении задачи 60 - не зря же дана ссылка на неё.
↓↓ 0 ↑↑   PetrK (14 / 7)   20 фев 2013 12:51   «« #5 »»   Ответить


С педагогический точки зрения, ответ на вопрос и объяснение, что он верный — это называется «ответ». А «решение» — это описание пути (!) от условия до ответа. В данном случае куда более интересно именно решение, а не ответ.
↓↓ 0 ↑↑   eruditor (89 / 438)   25 фев 2013 20:15   «« #6 »»   Ответить


Согласен, но...
Это всё же всего лишь "подзадача" для основной задачи номер 60. Там был предложен алгоритм для заключенных - сопоставить каждый ящик заключенному, и ходить по ним в соответствии с найденными бумажками. Здесь же стояла задача (для меня во всяком случае) понять в каких случаях он не работает, а затем понять, может ли одно пепремещение бумажек исправить ситуацию. В таком ключе рассуждения выше - это именно последовательный путь к ответу. А то как был придуман основной алгоритм лучше поискать в задаче 60. Видимо, из эмпирических соображений - выбор 50 ящиков случайным образом не использует той информации, которая у нас есть (бумажки). Вот и был придуман алгоритм, который как-то использует бумажки, а потом оказалось (если мне память не изменяет, строго там вероятность никто не доказывал, только моделировали) что такой способ годится.
↓↓ 0 ↑↑   PetrK (14 / 7)   08 мар 2013 15:46   «« #7 »»   Ответить


Так а каким именно образом этот способ "использует информацию, которая у нас есть (бумажки)"?
↓↓ 0 ↑↑   eruditor (89 / 438)   09 мар 2013 08:06   «« #8 »»   Ответить


Так, первый заходит — находит свое имя, и переставляет его таким образом, чтобы он стал первым. Заходит второй по счету узник и уже первый ящик не просматривает, а начинает со второго и найденный ящик переставляет на место второго ящика и так далее. Просто они заранее должны это обговорить. Каждый знает каким по счету он зашел — вот и все) Все спасиены и мир во всем мире)))
↓↓ 0 ↑↑   ольга говорус (0 / 1)   18 янв 2015 17:05   «« #9   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы