Форум умных людей

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

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

Я не совсем понял - " сначала лапочка выключена" -   ее периодически включают или как.

Ее можно включать заключенным, ведь "он может зайти в эту комнату и делать все, что хочет в течение минуты" (в одном из решений включать необходимо, ну и в авторском конечно)

У меня тока вот что надумалось:
Я так понял что им дали посоветоваться перед тем как их посадили.
Выбираем 1 человека который будет непосредственно общаться с охраной.
Все кроме него будут при попадании в комнату включать лампу, а этот единственный ее гасить, причем каждый может зажечь лампу лишь 1 раз, и если он пришел, а лампа уже горит, то он ее не трогает.
Когда человек выключающий лампы насчитает 99, то можно смело говорить что все побывали в комнате!

по отпечаткам пальцев навыключателе  можно докозать что  все побывали в комнате . Если раньше кто то несколько раз  выключал  свет  то  тогда  в начале  нужно стереть прежние  и  проделать это сного поочередно.

В течении минуты по отпечаткам проверить это тяжело. А заключенных пускают хаотично (кого-то могут запустить только через год) и они друг друга больше никогда не видят. В вашем варианте нет 100% шанса на освобождение.

П.С. Первый ответ очень сложный. Второй и третий на смекалку, но третий еще и шуточный. И все ответы полностью удовлетворяют условию задачи.

Да :) Это упрощенный вариант первого ответа. Но только с охраной он не общается.
Вот английская версия ответа http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf

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

Уже лучше, но не совсем так :) Гораздо проще :D

А у меня вопрос к вам насчет http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf Что там написано так много?! :o ::)

можно ещё к имени в списке добавить дату посещения, пришёл дважды, поставь вторую дату, по-моему проще некуда, я даже не верила, что такой ответ может быть правильным!

Большой список получится. За минуту точно проанализировать сложно. Эксперимент-то может длиться около 5 лет

блин каждый заключеный пишет токо одну цифру на стене за все посещения первый-1 второй-2 третий-3 и если они опять заходят в комнату то не увидя число 100 ничего не говорят

Верно. Остался шуточный ответ на тупую смекалку

Я на счет шуток здаюсь

Я вас понимаю. Сам не люблю шуточных вопросов и ответов, просто не могу их понять. Но этот ответ меня немного рассмешил (прочитал на одном из форумов этой задачи)

каждый заключенный приходя в камеру убивает себя, таким образом 1 душа будет спасена

 :D :D :D Оригинально, ничего подобного еще не видел. Со смекалкой проблем нет  :D :D :D Но третий ответ без смертей (думаю различных ответов очень много)

1 решение: каждый кто входит 1 раз опускает рубильник , один из всех заключеных может его поднимать (он то и и узнает сколько всего было заключенных)

Вопрос!
Есть два варианта!
В первом заключенный включает свет, он попал в камеру первый раз. Выключает рубильник только один, который и считает.
Во втором заключенные выключают свет, если первый раз. Выключает рубильник считающий.

Является ли это двумя вариантами (способами) решения данной задачи? Если нет, то будем думать!

точно 99 раз поднял - значит все побывали
решение оказалось простым :)

да, являются
задача решена

второй вариант (все счетчики)
подсказка: счетчиков будет меньше становиться
Показать скрытый текст

Предположим , что счётчику не везёт, и его долго не водят в эту комнату.
Все уже зашли по 2 раза, и наконец привели счётчика 1-й раз. Он видит что свет горит, значит минимум 1 там побывал.
Снова все зашли по 2 раза, завели счётчика, он видит что двое там побывали.
В этот момент их расстреливают, так как все побывали минимум по 2 раза, а кто-то 3 раза. Но счётчик этого так и не узнал. С этим дополнительным (выделенным красным) условием задача не имеет решения.
 

передумал

что бы все было быстро+ те ограничения что мне давали (сейчас можно говорить что их нету и т.п. но все ограничения не обговоришь в условии), а это есть только рубильник, который может быть только в 2х положениях, больлше ничего , он не затерается и т.п. так не получится, простой пример:  всех заводят по 3 раза (сначала первого 3, потом второго .......)

Честно не понял. Если только один выключает свет то где гарантия что его через одного не приведут опять в комнату?

1) второй способ хоть кто то читал?
2)под данну задачу оно не сработает( я сомневаюсь можно ли доказать с помощью кода 0 и 1 что данная задача решается, выше описал ) , без учета условия "но если все побывали по два раза, а кто-то три" ( как в другом посте)  , а если только один включает, то ему нужно подсчитать сколько людей было , ну и пусть что его через одного приведут, что из этого? он опять рубильник поднимит(если был опущен)
Можно узнать, е задача копипастилась? именно такая формулировка была в оригинале?

Возможно, имеется в виду следующее(или что-то в этом роде):

Заключённого, которого привели в первый день, назовём "счетчик", остальных назовём "простые".
Простой, если зашёл в тёмную комнату, не трогает рубильник.
Если зашёл в светлую комнату первый раз, выключает свет.
Во второй и последующие разы в светлой комнате простой не трогает рубильник.
Счётчик всегда включает свет (или, если свет горит, не трогает рубильник).

счетчик только поднимает , остальные только 1 раз опускают

Ну да, правильно.

Значит получается примерно так:
Например "простой" заключённый А зашёл в первый раз. Свет горит, он его тушит-это сигнал счётчику что ещё один "простой" зашёл в комнату. Потом могут зайти несколько "простых", они рубильник не трогают. Наконец заходит "счётчик", видит что кто-то потушил свет, понимает что ещё один "простой" заходил, прибавляет к количеству зашедших 1, снова включает свет. Даже если "простой" А зайдёт ещё раз, он больше рубильник никогда не тронет, поэтому его посчитают только 1 раз. Возможно "счётчик" зайдёт следующие несколько раз, это ничего не меняет. Дальше заходит "простой" В, видит - свет горит, тушит свет. Когда "счётчик" снова зайдёт, он увидит что свет потушен, значит ещё один заходил, и т.д., пока все 99 не зайдут.

Плохо будет, если счётчик самый первый зашёл в комнату, а свет выключен...
 :)
Но по моему это самое лучшее решение...

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

а это уже противоречит вот этой части условия

Из условия: бывают такие случаи, что приводят одного и того же по сто раз подряд.

так одного и того же
а в условии сказано про всех допустим счетчика привели после того как все уже побывали там по разу, он врубает рубильник
следующий - не счетчик заходит и вырубает, потом опять заводят счетчика и опп - всех казнят, так как все побывали по два раза :help:

если из условия убрать вот эту часть то все нормально сходится
А у вас в условии lkob этой части не было, так что ваша задача решена.

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

Из условия: но если все побывали по два раза, а кто-то три, то их также на следующее утро всех расстреливают.

Я знаю только то решение, когда есть один заключенный, который считает! Если взять тот факт, что условие задачи предполагает возможность, что все заключенные могут побывать в камере по 999 раз, а тот единственный, который выбран считающим, не был еще ни разу (охрана случайным образом выбирает заключенных), то получается несоответствие, т.к. считающему как минимум надо будет 99 раз быть в камере!

Условие, которое задавали мне не содержало фразу о том, что если все были по два-три раза, то их расстреливают.

Широков, абсолютно согласен! Но это не решение, если существует хоть маленькая вероятность, что при неких условиях оно не работает!

я и говорю - ваша задача решена :good:
а вот эта ???

Согласен, Илья. Но тогда принципиально решение должно отличаться, т.к., как я уже писал, если выбрать одного избранного, который должен считать, то всех могут вызывать по множество раз, а его только спустя долгое время... А ведь ему, считающему, надо побывать не менее 99 раз!

какая разница он первый или нет? больше 3х раз скорее всего все будут(очень маленькая вероятность при данном решении что будут меньше 3х раз)
ещё раз привожу пример: заводят всех по 3 раза, сразу же, и как с помошью 1 или 0 передать информацию что тут были все?тут явно должно быть какое нить снисхождение по сравнению с задачей lkobа

Kot, согласен! Хотя, можно подумать! А вдруг существует другое, принципиально другое решение, которое удовлетворяет всем условиям задачи!

каждый , кто заходит впервые , делает в уголку кучку, а потом счтают их количество

оказывается тут на стенках можно писать О_о и чем же она тогда труднее?? вообще в чем сложность?

 :laugh: :laugh: :laugh:

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

Как это он не знает? Он же знает что сегодня первый день, значит до него никого не было.

Придумал продолжение про 100 заключённых. Выкинул неправильное условие про "если все побывали по два раза, а кто-то три". Теперь заявление должны сделать не один а два заключённых. Поместил в авторские задачи: Заключенные -2 (http://nazva.net/forum/index.php/topic,2904.0.html)

Извините, спутал, там не каждый день а каждый час. Если он не знает, что он первый, то да-проблема. Зависит от формулировки.

а можно узнать источник? хотелось бы там прочитать, уж очеееень сомневаюсь что есть ограничения на время(2-3 раза макс заходят)

 Вопрос к автору задачи!
Есть ли решение, при условии, что заключенные должны быть вызваны не более 2-3-х раз?

P.S. Что-то не получается решить...

Скорее всего ошибка автора.

Автор уже не появлялся около полугода

куда не загляну, везде одни заключённые, кошмар! :skull:

Ага ;D жратва ,заключенные и долбогрызы ;D ;D ;D

Согласна с тобой Маша, не на то мужчины направляют свои усилия! :wall:

Ой, :pinkgirl:а про долбогрызов то я :(

розовые очки советую не снимать ( даже временно) с ними веселее  :haha2:

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

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

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

Хмм, мне кажется так, или ,возможно, я не совсем правильно понял условие задачи......
Нужно чтоб к тому времени, когда заидет единственный оставшийся, который еще ни разу не заходил, остальные там побывали не более 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 час ....
  :D
И ,естественно, тот вариант задачи, который  я себе представил имеет краине малый шанс срабатывания - шанс того , что все 100 заключенных однажды побывают в камере не более 1 го раза с момента последнего повторения номеров ....