В тюрьме содержатся 100 узников. Однажды их собирают во дворе и объявляют, что проведут с ними испытание. Состоит оно в следующем:
В одной из камер расставлены в ряд 100 ящиков. В каждый из них положена бумажка с именем одного из узников, причём в разные ящики — разные имена. Узников по одному будут заводить в эту камеру. В камере узник может открывать и заглядывать в те ящики, которые хочет, но максимум он может открыть 50 ящиков из 100. Его задача в том, чтобы среди открытых им ящиков оказался тот, в котором лежит бумажка с его именем.
После этого его уведут и сразу отправят в свою камеру. Уходя, он должен оставить камеру точно в том же состоянии, в котором её нашёл. Таким образом, в процессе испытания никакого обмена информацией между узниками нет.
Узников выпустят, если КАЖДЫЙ из них найдёт бумажку со своим именем, в противном случае всех казнят. У них есть время перед началом испытания, чтобы договориться о стратегии, которая позволит выиграть с максимальными шансами.
В честь празднования Нового года начальник тюрьмы смягчил правила испытания, позволяя первому заходящему в камеру узнику осмотреть содержимое всех ящиков и, если захочет, поменять местами любые два (и только два) из них.
Найдите стратегию, которая позволит узникам гарантированно (со 100% вероятностью) успешно справиться с этим испытанием.
Решение Так же как и в 60 задаче представим эти ящики как множество циклических списков - если в ящике с именем "Миша" лежит записка "Миша", то ящик ссылается сам на себя (список "Миша"->"Миша"), если там лежит "Маша", а "Маша" ссылается на "Миша", то есть список "Миша"->"Маша"->"Миша" и т.д. Понятно, что если каждый заключенный начинает просмотр со свого ящика, то он должен дойти по списку до себя же не более чем за 50 шагов. Также понятно, что может существовать тольо один цикл длиной X > 50 ящиков (т.к. всего 100 ящиков и длина оствшихся циклов будет меньше или равна 100 - X). Теперь возьмём любой ящик из этого цикла, отсчитаем от него X/2 ящиков и поменяем в них бумажки - теперь у нас есть вместо большого цикла два маленьких, длиной X/2. Длина всех циклов < 50, значит все заключенные выживают.
Это не ответ. Это решение. Изложен план действий для заключенного и объяснено почему он сработает. Это называется решение. Всякие ненужные подробности типа как найти максимальный по длине цикл (прошли один цикл, переходим к первому непосещённому ящику) или почему списки циклические (показывается от противного или даже просто из принципа Дирихле) я опустил.
С педагогический точки зрения, ответ на вопрос и объяснение, что он верный — это называется «ответ». А «решение» — это описание пути (!) от условия до ответа. В данном случае куда более интересно именно решение, а не ответ.
Согласен, но... Это всё же всего лишь "подзадача" для основной задачи номер 60. Там был предложен алгоритм для заключенных - сопоставить каждый ящик заключенному, и ходить по ним в соответствии с найденными бумажками. Здесь же стояла задача (для меня во всяком случае) понять в каких случаях он не работает, а затем понять, может ли одно пепремещение бумажек исправить ситуацию. В таком ключе рассуждения выше - это именно последовательный путь к ответу. А то как был придуман основной алгоритм лучше поискать в задаче 60. Видимо, из эмпирических соображений - выбор 50 ящиков случайным образом не использует той информации, которая у нас есть (бумажки). Вот и был придуман алгоритм, который как-то использует бумажки, а потом оказалось (если мне память не изменяет, строго там вероятность никто не доказывал, только моделировали) что такой способ годится.
Так, первый заходит — находит свое имя, и переставляет его таким образом, чтобы он стал первым. Заходит второй по счету узник и уже первый ящик не просматривает, а начинает со второго и найденный ящик переставляет на место второго ящика и так далее. Просто они заранее должны это обговорить. Каждый знает каким по счету он зашел — вот и все) Все спасиены и мир во всем мире)))
100% вероятность, что все узники найдут бумажки со своими именами возможна только в случае, если каждый узник может переставлять по 2 ящика. 1.Первый открывает все ящики и находит свое имя; 2.Переставляет ящик со своим именем первым; 3.Зная кто идет за ним, ставит ящик с именем второго вторым; 4. Уходит 5.Заходит второй, вскрывает второй ящик со своим именем и еще 49 ящиков по порядку (слева направо) в поисках имени третьего; 5.1.В случае если находит ставит этот ящик третьим; 5.2. Если не находит, то оставляет все как есть; 6. Уходит; 7.Заходит третий, проверяет третий ящик; 7.1.Если находит свое имя, то проверяет по порядку от четвертого ящика еще 49 ящиков в поисках имени четвертого; 7.1.1. Находит и ставит его четвертым по счету; 7.1.2.Не находит, то уходит и ничего не меняет 7.2.Если не находит своего имени в 3 ящике, то проверяет 49 ящиков, отсчитывая с правого конца. Находит 100% и ставит свой ящик третьим Ну а дальше все по этому алгоритму до конца. В итоге все 100 узников найдут бумажки со своими именами
Первый имеет право только на одну перестановку. Не имеет значения каким будет стоять его имя. Наверно он просто ставит ящик с именем следующего за ним на первое место. Без возможности каждого переставлять по два ящика тоже не вижу решения
