Надо сказать, что красивые, нетривиальные задачи появляются на свет нечасто. Эта задача была придумана меньше года назад, но уже сейчас ясно, что у нее есть все шансы стать, что называется, классической.
Итак, условие.
- (Да, прошу тех товарищей, кто эту задачу знает, не выскакивать с решением, а дать спокойно подумать и порассуждать другим товарищам)
Сто заключенных сидят в своих одиночных камерах в ожидании смертной казни. В один прекрасный день администрация тюрьмы собирает их всех в актовом зале, и объявляет следующее:
- Мы даем вам шанс на жизнь. Вот здесь под потолком, видите, висит лампочка. Вот для нее выключатель на стене. Сейчас лампочка выключена. Мы будем каждые сутки, начиная с завтрашнего дня, совершенно случайным образом выбирать одного из вас и заводить его на минуту в эту комнату. Пока вы в комнате, вы можете включить или выключить лампочку, или ничего не трогать.
Кроме того, любой из вас, будучи в комнате, имеет право заявить, что все сто заключенных уже побывали хотя бы по разу в этой комнате. Если ваше заявление окажется верным, все будете отпущены на свободу. Если неверным - все будете казнены немедленно.
Мы оставляем вас всех вместе здесь до завтрашнего утра, чтобы вы могли обсудить и выработать план действий. Завтра утром вы будете разведены по своим камерам и более не сможете друг с другом общаться.
