Страниц: 1 ... 3 4 [5]
  Печать  
Автор Тема: Заключенные  (Прочитано 29764 раз)
0 Пользователей и 1 Гость смотрят эту тему.

В тюрьме в одиночных камерах содержится 100 заключённых, приговоренных к пожизненному заключению. Есть также одна центральная комната с вечной лампочкой, которую охранники никогда не трогают. В комнате никогда не убираются, и охрана не замечает ничего подозрительного. Сначала лампочка выключена. Горит она или нет - из камер не видно. Каждый час охрана случайно выбирает одного заключённого для допроса (бывают такие случаи, что приводят одного и того же по сто раз подряд), и он может зайти в эту комнату и делать все, что хочет в течение минуты. Также у него есть право сделать заявление о том, что все 100 заключённых побывали в этой комнате. Если его утверждение истинно, всех заключённых выпускают. Если утверждение ложно, то следующим же утром всех расстреливают, но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают. Поэтому такое заявление следует делать только при 100% уверенности и как можно раньше. Перед началом "эксперимента" заключённые могут собраться и выработать план. В дальнейшем все контакты между ними исключены.
Как нужно поступить заключенным, чтобы выйти на свободу?

П.С. Задача сформулирована мной так, что имеется как минимум три различных решения. Но есть авторское очень сложное решение на английском, поэтому понять его я так и не смог.
 
Наталия
Сплошной мозг
***
Offline Offline

Сообщений: 3696

СПАСИБО
-вы поблагодарили: 168
-вас поблагодарили: 185



Просмотр профиля
Ответ #60 : Март 04, 2010, 00:10:32 �

розовые очки советую не снимать ( даже временно) с ними веселее  Ха ха
Записан
Kot
Новенький
*
Offline Offline

Сообщений: 49

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3


Просмотр профиля Email
Ответ #61 : Март 04, 2010, 13:57:06 �

Показать скрытый текст


не упрощает доп условия (хоть кто то должен побывать не больше 1 раза, или все 2 раза)
Записан
Kot
Новенький
*
Offline Offline

Сообщений: 49

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3


Просмотр профиля Email
Ответ #62 : Март 04, 2010, 14:02:55 �

как можно обсуждать без автора? когда всех ограничений не знаешь (нет ограничений-рисуем числа на стене, общаемся в камерах, даем взятки охранникам, у каждого есть ТВ и идет трансляция из той комнаты и т.п.)

Эти пользователи сказали вам СПАСИБО :

??????????__

За это сообщение 1 пользователь сказал спасибо!
Записан
Zeus
Новенький
*
Offline Offline

Сообщений: 1

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #63 : Ноябрь 09, 2010, 12:47:47 �

Первый разбивает лампочку и кладет один осколок в определенное место(оговоренное зарание). Последующие тоже кладут осколок. Если уже был - ни чего не кладешь. как только будет 100 осколков - все СВОБОДА.
Записан
DarkBlade
Новенький
*
Offline Offline

Сообщений: 2

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля Email
Ответ #64 : Ноябрь 10, 2010, 11:12:48 �

Хмм, мне кажется так, или ,возможно, я не совсем правильно понял условие задачи......
Нужно чтоб к тому времени, когда заидет единственный оставшийся, который еще ни разу не заходил, остальные там побывали не более 1 го раза? 

Если да, то это трудно представимо... но вполне решаемо.....

Если у нас,допустим, такая последовательность посещений комнаты допросов (по номерам заключенных) : 1 36 72 44 48 96 94 36..... Значит 36й заключенный заходит в комнату допросов второй раз....и он должен оставить отметку для остальных о том, что он уже не первый раз здесь, чтобы тот кто будет считать с начала знал об этом. Допустим заключенные оставляют пометки на стенах в виде строки из своих номеров. Если 36й вторично попал в комнату, значит цикл в котором все заходят в комнату в первый раз нарушился - 36й попал в комнату еще раз. Тогда цикл, в котором все побывали в комнате 1 раз нужно начинать отсчитывать заново, но можно начинать не с 36 го,а с того чеи номер стоял за 36м во время его предыдущего посещения.  То есть в нашем случае с 72 го... (72 44 48 96 94 36) - таким образом снова никто не побывал в комнате допросов больше 1 го раза. Значит в этом случае каждый оставляет пометку - свой личный номер в строке.  Тут начинается самое ,на мой взгляд, неправдоподобное. Каждый заключенный, поставив свои номер, считает сумму последних 100 чисел в строке.   Он знает заранее, чему равняется сумма всех чисел от 1 до 100 (думаю за столько времени посчитать он сможет, или в то время, пока им дадут 1 час самый умный из них посчитает и скажет остальным). Одна проблема -  посчитать сумму последних 100 чисел в строке на стене за 1 час ....
  Cheesy
И ,естественно, тот вариант задачи, который  я себе представил имеет краине малый шанс срабатывания - шанс того , что все 100 заключенных однажды побывают в камере не более 1 го раза с момента последнего повторения номеров ....
Записан
Страниц: 1 ... 3 4 [5]
  Печать  
 
Перейти в: