Задачка
В некоторой тюрьме содержится сотня узников. Тюремное начальство любит жестокие интеллектуальные шутки, но спрведливо и порядочно. Всех узников собирают в специально отведённой для этого комнате, в которой нет ничего, кроме единственного рубильника, включающего и выключающего в ней небольшую лампу. Собрав там узников, им объявили, что начинается следующая игра: после того как их снова разведут по одиночным камерам, случайно будут выбирать кого то из них и в произвольный момент времени приводить в эту комнату (по одному, разумеется) оставлять там на пару минут и затем снова уводить в камеру.
Например,одного узника могут привести туда уже в пятый раз, в то время как другого — ни разу. Как бы долго это ни длилось, рано или поздно в этой судьбоносной комнате побывают ВСЕ, и по нескольку раз. Если в какой-то момент один из узников заявит, что в комнате побывали все 100, то все они будут отпущены на свободу. Если он ошибётся, то всех казнят. Сообщив условия жестокой игры, узников оставили в комнате на полчаса, чтобы они могли поболтать о том, о сём. Затем их развели по камерам , и началась игра. О какой стратегии должны были договориться узники, чтобы освобождение стало возможным?
Ограничения: писать нехорошие слова на стенах комнаты строго запрещено…мммм…даже палочки рисовать. Перестукиваться, кричать или подавать любые звуковые сигналы строго запрещено. Разрешается только включать, либо выключать рубильник: он остаётся включенным или выключенным до прихода следующего узника.
(c) rsdn.ru
Думал думал думал думал, ничего хорошего не придумал =)
Как в одном бите хранить инфу про 100 заключенных хз …
1-е утверждение. Если это вообще можно узнать, то узнать это может
только человек, попавший в комнату как минимум второй раз, и вывод
он может сделать только на основании состояния рубильника. (Кстати,
насчёт 1 бита информации ты неправ, у рубильника есть не только
состояния вкл выкл, а ещё начальное состояние)
У нас есть: начальное состояние рубильника и состояние рубильника
в момент времени, когда туда зашёл заключнный.
Но, заключённый может либо вкл либо выкл рубильник. Причём всего лишь
по одному условию: в первый раз он появился в комнате или нет, потому что
больше он ничего не знает. Т.е., например:
Начальное состояние рубильника: выключен. Заключенный заходит в первый раз,
видит выкл рубильник и вкл. его. Если заходит второй раз, состояние
рубильника не меняет (с точки зрения информативности достаточно уже того,
что один раз он там побывал). Заходит следующий заключёный: Видит вкл.
рубильник и выкл. его. И т.д. Причём: если первый заключённый заходит
второй раз и видит: рубильник вкл., значит в комнате побывало кроме него:
там либо никого не было, либо было чётное число народа. Т.е.
можно гарантираванно сказать только то, что 100 человек там не было,
если рубильник вкл. (Число заключённых не играет роли в этой задаче, кстати)
Какие бы варианты ты не перебирал:
Начальное сост.: вкл, при входе первый раз: не менять сост.
Нач. сост.: выкл, при входе первый раз не менять сост.
Нач. сост.: вкл, при входе первый раз менять
Нач. сост.: выкл, при входе первый раз менять
Ни один из четырёх вариантов не позволит сказать о том, побывали
ВСЕ узники в комнате или нет.
В задаче не хватает данных. Ну можно конечно изголица, и сказать, что
они выкручивают лампу вначале, тогда появляеца ещё один заключённый, который знает, что он пришёл в комнату первым. Но это тоже не поможет.
В задаче нехватает условий.
Ну или какие-нить такие извращения типа:
Узники пронумеровали себя. Каждый кто заходит переключает рубильник
столько раз, какой у него номер, если он туда первый раз зашёл. Но это опять таки не поможет.
Климыч ты лошпет, несбивай людей. Все не так грустно. //Т34
Ну в общем да. Надо выбрать чела, который будет запоминать, сколько раз он выключил рубильник
Го в Шуколово на любительский SBX завтра в 14.00.
http://www.onboard.ru
Накатал то =)
Хе!
Все равно всех казнят :-)
На самом деле вопрос о распространении информации. И хранение данных там распределенное. Т.е. зеки сами о себе знают, были ли они в камере с тумблером.
Если зеки не общаются между собой, то единственный способ передачи и консолидации информации — в том тумблере в камере, в которую всех водят.
Однако нет никакой возможности понять, всех ли (каждого ли) водили в камеру хотя бы по одному разу, поскольку выборка производится спонтанно. По исключению это сделать возможности нет, поскольку один бит действительно не в состоянии описать появление или отсутствие 100 зеков. А иначе сделать не получится…
Решение существует =)
Выбирается один «пахан», который считает сколько раз включен свет. Другие только при первом заходе, когда выключен свет его включают в остальные разы ничего не делают. Когда пахан насчитает 99 можно говорить «Все были».
так он может попасть туда всего один раз ;)
Как бы долго это ни длилось, рано или поздно в этой судьбоносной комнате побывают ВСЕ, и по нескольку раз.
А если я захожу, а свет включен? и я первый раз? ждать второго? что-то не то.
Ну 100 раз — один раз резервный.
Я тут подумала, и поняла, что это самое точное решение, чтобы каждый, кто заходит, включал свет, если он, не включен, каждый человек один раз. То есть отмечался.
Допустим, пахан считает.
Чтобы всех посчитать он должен побывать в комнате как минимум 100 раз.
То есть вероятность того, что он 1раз побывает один делить на 100.
А чтоб 100 раз, наверное, 1 делить на 10000.
Нужно, чтобы процедура провелась 10000 раз. И это в лучшем случае, если все по очереди будут попадать.
Люди столько в неволе не живут!! И лампочки тоже. В один прекрасный день она перегорит :)
Элегантное решение, но нереальное.