Каморка

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

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

Итак, условие.

• (Да, прошу тех товарищей, кто эту задачу знает, не выскакивать с решением, а дать спокойно подумать и порассуждать другим товарищам)

Сто заключенных сидят в своих одиночных камерах в ожидании смертной казни. В один прекрасный день администрация тюрьмы собирает их всех в актовом зале, и объявляет следующее:

• Мы даем вам шанс на жизнь. Вот здесь под потолком, видите, висит лампочка. Вот для нее выключатель на стене. Сейчас лампочка выключена. Мы будем каждые сутки, начиная с завтрашнего дня, совершенно случайным образом выбирать одного из вас и заводить его на минуту в эту комнату. Пока вы в комнате, вы можете включить или выключить лампочку, или ничего не трогать.
  
  Кроме того, любой из вас, будучи в комнате, имеет право заявить, что все сто заключенных уже побывали хотя бы по разу в этой комнате. Если ваше заявление окажется верным, все будете отпущены на свободу. Если неверным - все будете казнены немедленно.
  
  Мы оставляем вас всех вместе здесь до завтрашнего утра, чтобы вы могли обсудить и выработать план действий. Завтра утром вы будете разведены по своим камерам и более не сможете друг с другом общаться.

Смогут ли узники выйти на свободу? Если да, то что они должны делать?

Смогут ли узники выйти на свободу? Если да, то что они должны делать?

1. перестукиваться.
2. оставлять запись на стене "здесь был Вася"

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

Если бы каждого заключенного можно было заводить в комнату только один раз, то все просто, надо подождать 100 дней. Если же каждый может побывать несколько раз, то надо как-то передавать информацию о количестве повторных посещений. Для этого наверно надо использовать лампочку. Однако лампочка может хранить только один бит информации: нуль или единица. Если бы она хранила количество переключений, то было бы просто.

просто мысль: Например, человек может включать лампочку при повторном посещении, а при первом гасить, если она включена. Но это тоже ничего не дает.

В общем надо подождать достаточно долго, тогда вероятность, что все побывали, увеличится.

Если на карте жизнь, то надо наверняка.

Akrav писал(а):Если на карте жизнь, то надо наверняка.

Иногда надо рисковать.

Alexan писал(а):

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

Если бы каждого заключенного можно было заводить в комнату только один раз, то все просто, надо подождать 100 дней. Если же каждый может побывать несколько раз, то надо как-то передавать информацию о количестве повторных посещений. Для этого наверно надо использовать лампочку. Однако лампочка может хранить только один бит информации: нуль или единица. Если бы она хранила количество переключений, то было бы просто.

просто мысль: Например, человек может включать лампочку при повторном посещении, а при первом гасить, если она включена. Но это тоже ничего не дает.

В общем надо подождать достаточно долго, тогда вероятность, что все побывали, увеличится.

Этой информации недостаточно. Надо учесть еще номер текущего дня.
Очевидно, что первые 100 дней не все еще побывали. Я думаю надо какую-то операцию проделать типа посчитать четность дня, количество посещений а лампочка показывает 1-битный результат.

Мне кажется, что
1. Заключенных надо пронумеровать (от 1 до 100)
2. Проверка должна быть накопительной, т.е. неважно если только №37 не был в комнате, важно, что 36 человек прошло
3. Должна быть привязка к дате
4. Это может оказаться очень долгий процесс.

И еще есть рекуррентность в смысле я знаю свои количество посещений и день первого посещения плюс один бит информации от того, кто был здесь вчера.

Я как бы нашел решение, но его практическая ценность очень мала, т.к. скорее всего заключенные раньше умрут от старости

Мне кажется, я решил задачу.
Если это так, я разачарован.

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

Ибо они не только там были, но и также провели там ночь - Мы оставляем вас всех вместе здесь

Alexander Ch. писал(а):Мне кажется, я решил задачу.
Если это так, я разачарован.

Почему же разочарован? По моему очень хорошая загадка.
Цинику: неужели сам придумал?

Alexander Ch. писал(а):Я как бы нашел решение, но его практическая ценность очень мала, т.к. скорее всего заключенные раньше умрут от старости

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

типа такого ?

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

Смогут выйти на свободу.
Кажый должен отвечать - Да, все уже были минимум по разу в этой комнате.

Давайте разберем первые полеты, товарищи

Lepsik писал(а):1. перестукиваться.
2. оставлять запись на стене "здесь был Вася"

И то и другое запрещено. Под страхом смерти

Alexan писал(а):Если же каждый может побывать несколько раз

Именно так.

Alexan писал(а):надо как-то передавать информацию о количестве повторных посещений. Для этого наверно надо использовать лампочку. Однако лампочка может хранить только один бит информации: нуль или единица. Если бы она хранила количество переключений, то было бы просто.

Ага. В этом и соль задачи. Бит один, а необходимой информации-то вроде как поболе.

Alexan писал(а):В общем надо подождать достаточно долго, тогда вероятность, что все побывали, увеличится.

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

Alexander Ch. писал(а):1. Заключенных надо пронумеровать (от 1 до 100)

Нумеруйте, почему же нет, никто этому не препятствует.

Alexander Ch. писал(а):4. Это может оказаться очень долгий процесс.

Может. А может, и нет.

Alexander Ch. писал(а):Я как бы нашел решение, но его практическая ценность очень мала, т.к. скорее всего заключенные раньше умрут от старости

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

Alexander Ch. писал(а):Первый же заключенный в самый первый день может сказать, что все сто заключенных уже побывали хотя бы по разу в этой комнате.
Ибо они не только там были, но и также провели там ночь - Мы оставляем вас всех вместе здесь

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

Alexan писал(а):Цинику: неужели сам придумал?

Ну что ты, товарищ. Я скромнее - свои задачи сам классическими не называю

Да, красиво.