Тюремщик

Тюремщик встречает 23 новых заключенных и говорит:

Сегодня вы можете встретиться и выработать стратегию, но после этого вы будете изолированы в своих камерах и не сможете общаться.

В тюрьме есть комната с двумя выключателями «А» и «Б», каждый из которых может быть либо включен, либо выключен. В каком они сейчас положении я вам не скажу. Выключатели ни к чему не подключены. С завтрашнего дня я начну время от времени, когда мне этого захочется, брать одного из вас и приводить в эту комнату. Он должен будет выбрать один из выключателей, включить его, если он был выключен или выключить, если он был включен. Потом я отведу его назад в камеру. Никто кроме вас не будет входить в эту комнату и изменять положение выключателей.

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

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

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

(Своровано из Ponder This. Я решил. Оказывается, не так-то уж и трудно.)

Популярное
3 комментария
РезиновыйЗапаЛ 2004

Да, подозрительно синхронно по времени выбирает направление Илья и <a href=http://register.spectator.ru/03.03.2004/4/comments>Спектатор</a>, да и темки перекликаются. Что-то меня здесь смущает.

Baka 2004

Что здесь значит «с завтрашнего дня»?
Что он приведёт кого-то завтра,
а остальных — в какие-то из следующих дней? Если так, то я знаю,что делать.

Или он и первого может привести только через месяц?

Илья Бирман

Честно говоря, я не вижу никакой разницы в том, через сколько приводить первого. Или вы имеете в
виду, может ли заключенный посчитать, сколько в принципе визитов уже произошло за некоторое
количество дней? Нет, не может. Заключенных тюремщик водит в switchroom когда ему захочется, то есть
первого он, разумеется, может отвести через месяц. А потом в течение 5 минут остальных сводить по 10
раз.

Baka 2004

Или вы имеете в

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

Нет, я имел в виду — может ли он определить, что до него совсем никого не было (то есть, что он первый).

Илья Бирман

Скажем так, ни в моём решении, ни в решении, предложенном на IBM.com это не требуется. Следовательно, исходите из того, что он никак не может определить первый он или нет.

Мои книги