В тюрьме в одиночных камерах содержится 100 заключённых, приговоренных к пожизненному заключению. Есть также одна центральная комната с вечной лампочкой, которую охранники никогда не трогают. В комнате никогда не убираются, и охрана не замечает ничего подозрительного. Сначала лампочка выключена. Горит она или нет - из камер не видно. Каждый час охрана случайно выбирает одного заключённого для допроса (бывают такие случаи, что приводят одного и того же по сто раз подряд), и он может зайти в эту комнату и делать все, что хочет в течение минуты. Также у него есть право сделать заявление о том, что все 100 заключённых побывали в этой комнате. Если его утверждение истинно, всех заключённых выпускают. Если утверждение ложно, то следующим же утром всех расстреливают, но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают. Поэтому такое заявление следует делать только при 100% уверенности и как можно раньше. Перед началом "эксперимента" заключённые могут собраться и выработать план. В дальнейшем все контакты между ними исключены.
Как нужно поступить заключенным, чтобы выйти на свободу?
П.С. Задача сформулирована мной так, что имеется как минимум три различных решения. Но есть авторское очень сложное решение на английском, поэтому понять его я так и не смог.
|
Michael
Гость
|
 |
� Ответ #30 : Февраль 26, 2010, 03:35:47 � |
|
счетчик только поднимает , остальные только 1 раз опускают
Ну да, правильно. Значит получается примерно так: Например "простой" заключённый А зашёл в первый раз. Свет горит, он его тушит-это сигнал счётчику что ещё один "простой" зашёл в комнату. Потом могут зайти несколько "простых", они рубильник не трогают. Наконец заходит "счётчик", видит что кто-то потушил свет, понимает что ещё один "простой" заходил, прибавляет к количеству зашедших 1, снова включает свет. Даже если "простой" А зайдёт ещё раз, он больше рубильник никогда не тронет, поэтому его посчитают только 1 раз. Возможно "счётчик" зайдёт следующие несколько раз, это ничего не меняет. Дальше заходит "простой" В, видит - свет горит, тушит свет. Когда "счётчик" снова зайдёт, он увидит что свет потушен, значит ещё один заходил, и т.д., пока все 99 не зайдут. |
|
|
|
|
Записан
|
|
|
|
Широков
Давненько
 Offline
Сообщений: 112
СПАСИБО
-вы поблагодарили: 13
-вас поблагодарили: 9
Что видишь ты как ухо, то может быть как глаз...
|
|
� Ответ #31 : Февраль 26, 2010, 08:46:55 � |
|
Плохо будет, если счётчик самый первый зашёл в комнату, а свет выключен...  Но по моему это самое лучшее решение... |
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #32 : Февраль 26, 2010, 11:18:20 � |
|
Плохо будет, если счётчик самый первый зашёл в комнату, а свет выключен...
По условию мы знаем, что вначале лампочка выключена. Когда "считающий" зайдет в первый раз, то просто включит свет и считать не будет. И не важно, будет он первым, либо сотым... |
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #33 : Февраль 26, 2010, 11:23:52 � |
|
Плохо будет, если счётчик самый первый зашёл в комнату, а свет выключен...
По условию мы знаем, что вначале лампочка выключена. Когда "считающий" зайдет в первый раз, то просто включит свет и считать не будет. И не важно, будет он первым, либо сотым... а это уже противоречит вот этой части условия но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #34 : Февраль 26, 2010, 11:40:45 � |
|
Из условия: бывают такие случаи, что приводят одного и того же по сто раз подряд.
|
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #35 : Февраль 26, 2010, 11:44:14 � |
|
Из условия: бывают такие случаи, что приводят одного и того же по сто раз подряд.
так одного и того же а в условии сказано про всех все побывали по два раза допустим счетчика привели после того как все уже побывали там по разу, он врубает рубильник следующий - не счетчик заходит и вырубает, потом опять заводят счетчика и опп - всех казнят, так как все побывали по два раза  |
|
|
|
� Последнее редактирование: Февраль 26, 2010, 11:45:45 от Илья �
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #36 : Февраль 26, 2010, 11:56:06 � |
|
если из условия убрать вот эту часть но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают. то все нормально сходится А у вас в условии lkob этой части не было, так что ваша задача решена. |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Широков
Давненько
Offline
Сообщений: 112
СПАСИБО
-вы поблагодарили: 13
-вас поблагодарили: 9
Что видишь ты как ухо, то может быть как глаз...
|
|
� Ответ #37 : Февраль 26, 2010, 11:56:44 � |
|
По условию мы знаем, что вначале лампочка выключена. Когда "считающий" зайдет в первый раз, то просто включит свет и считать не будет. И не важно, будет он первым, либо сотым...
Даже если заключенные в курсе, что вначале лампочка выключена, счётчик то не знает выключена она была или её собратья выключили... Просто избранный обязательно должен выключать свет, а включать все остальные. То есть если он зашёл, а свет выключен, то он должен оставить его в этом положении и ждать, пока кто нибудь другой не включит... Конечно вероятность малая, что он первый попадёт, но всё же... |
|
|
|
|
Записан
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #38 : Февраль 26, 2010, 11:58:40 � |
|
Из условия: но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают.
Я знаю только то решение, когда есть один заключенный, который считает! Если взять тот факт, что условие задачи предполагает возможность, что все заключенные могут побывать в камере по 999 раз, а тот единственный, который выбран считающим, не был еще ни разу (охрана случайным образом выбирает заключенных), то получается несоответствие, т.к. считающему как минимум надо будет 99 раз быть в камере!
Условие, которое задавали мне не содержало фразу о том, что если все были по два-три раза, то их расстреливают.
|
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #39 : Февраль 26, 2010, 12:01:24 � |
|
Широков, абсолютно согласен! Но это не решение, если существует хоть маленькая вероятность, что при неких условиях оно не работает!
|
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Илья
Высший разум
Offline
Сообщений: 7695
СПАСИБО
-вы поблагодарили: 520
-вас поблагодарили: 1030
Терпение, мой друг, терпение...
|
|
� Ответ #40 : Февраль 26, 2010, 12:01:57 � |
|
Условие, которое задавали мне не содержало фразу о том, что если все были по два-три раза, то их расстреливают. я и говорю - ваша задача решена  а вот эта  |
|
|
|
|
Записан
|
Рост воровства у нас неудержим,
И мы кривою роста дорожим:
Раз все воруют, значит, все при деле!
На этом-то и держится режим!
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #41 : Февраль 26, 2010, 12:19:31 � |
|
Согласен, Илья. Но тогда принципиально решение должно отличаться, т.к., как я уже писал, если выбрать одного избранного, который должен считать, то всех могут вызывать по множество раз, а его только спустя долгое время... А ведь ему, считающему, надо побывать не менее 99 раз!
|
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Kot
Новенький
Offline
Сообщений: 49
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #42 : Февраль 26, 2010, 13:06:10 � |
|
какая разница он первый или нет? больше 3х раз скорее всего все будут(очень маленькая вероятность при данном решении что будут меньше 3х раз)
ещё раз привожу пример: заводят всех по 3 раза, сразу же, и как с помошью 1 или 0 передать информацию что тут были все?тут явно должно быть какое нить снисхождение по сравнению с задачей lkobа
|
|
|
|
|
Записан
|
|
|
|
Lkob
Умник
Offline
Сообщений: 625
СПАСИБО
-вы поблагодарили: 56
-вас поблагодарили: 62
Будь проще, и люди к тебе потянутся.
|
|
� Ответ #43 : Февраль 26, 2010, 13:13:10 � |
|
Kot, согласен! Хотя, можно подумать! А вдруг существует другое, принципиально другое решение, которое удовлетворяет всем условиям задачи!
|
|
|
|
|
Записан
|
Третий закон Ньютона даже наша партия не сумела отменить. Не успела. А зря...
|
|
|
Kot
Новенький
Offline
Сообщений: 49
СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 3
|
|
� Ответ #44 : Февраль 26, 2010, 21:53:06 � |
|
каждый , кто заходит впервые , делает в уголку кучку, а потом счтают их количество
|
|
|
|
|
Записан
|
|
|
|
|
