Задача про заключённых и лампочку.
В одной тюрьме сидели N заключённых, сидели, сидели, скучали. Но начальник тюрьмы был большой шутник, и решил он собрать всех заключённых. Собрал и сказал: «Каждый из вас сидит в одиночной камере. У нас есть одна свободная камера, в которую мы будем водить вас по одному человеку в случайном порядке с разными интервалами времени. Возможно, не по одному разу. В камере Вы будете 5-10 минут. В камере будет лампочка, которую можно включать или выключать, изначально она будет включена или нет — мы не знаем. Больше ничего делать нельзя. Когда кто-либо из Вас скажет, что все заключенные побывали в этой особой камере хотя бы один раз, я приму решение: если вы правы — освобожу всех, если вы ошиблись — так и будете сидеть до конца жизни здесь. Сейчас у вас будет время подумать и поразмышлять, через полчаса мы разведём вас по вашим камерам и начнём игру.»
Вопрос: какую стратегию должны выбрать заключённые, чтобы освободиться?
P.S.: заключённые не могут общаться между собой, оставлять послания или сообщения в спец.камере, видеть, кого ведут на допрос и т.п.
UPD:
Далее каждый обычный заключённый, заходя в комнату, будет включать лампочку, если она выключена, и он её включал менее 2-х раз.
Избранный заключённый, заходя в комнату, будет выключать лампочку и считать.
Когда он досчитает до
, то может сделать вывод, что все заключённые побывали в камере хотя бы один раз.
Могу высказаться по-поводу стратегии в общих чертах: каждый зайдя 1й раз включает лампу, а последующие разы (если случится) - выключает. Если какой-то заключенный побывает в камере с лампой X раз и в каждом случае найдет ее выключенной, то будет счиать, что побывали все.
Например, X=потолок(log2(N)). Другими словами решение основано, на том, что какой-то из зеков, Х раз последовательно побывав у лампы, пронаблюдает некую последовательность состояний лампы (7 походов для N=100). Эта и только эта последовательность будет "флагом", что хотя бы раз побывали все. Т.о. задача сводится к нахождению Х и определению условий появления "флага", а тот, кто еще не был, какждый раз сбивает "последоавтельность" флага.
Комментарий by Игорь — 26 июля 2011 @ 19:00