Синие и красные шапки

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

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

99 человек, а если повезет, то все 100 можно спасти следующим образом. Первый заключенный, рискуя своей жизнью, называет цвет впереди стоящего. Таким образом, у второго человека появляется информация о том, какой колпак у него на голове. Но он должен помочь следующему! Поэтому арестанты перед испытанием должны договориться о том, как они зашифруют информацию о цвете, если у впереди стоящего человека он отличается. Например, если цвет моей шапки красный, а у следующего в колонне тоже красный, то я говорю: «Красный». Если цвет шапки у следующего синий, то можно сказать: «Красный цвет» или «Красная шапка». Услышав дополнительное слово, тот, кто стоит впереди, поймет, какой цвет ему нужно будет назвать..

100 человек и 1 лампочка

100 человек из предыдущей задачки снова попали в тюрьму.

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

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

Что нужно придумать заключенным, чтобы их отпустили, при условии, что из других камер не виден свет из карцера?

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

• те, кто заходят в карцер в первый раз, должны включить свет, если он выключен или не трогать выключатель, если свет горит;
• те, кто заходят в карцер во второй раз, вообще не трогают выключатель;
• если счетовод попадает в камеру и видит, что свет горит, он его выключает и делает +1;
• если счетовод попадает в камеру, а свет выключен - он ничего не трогает.

Как только счетовод досчитает до 99, он может сказать надзирателям, что все заключенные побывали в камере.