2019-04-01
В тюрьму поместили 100 узников. Надзиратель сказал им: «Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной. Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ — скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут — если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним».
Придумайте стратегию, гарантирующую узникам освобождение.
Решение:
Узники выбирают одного человека (назовём его «счетоводом»), который будет действовать следующим образом. «Счетовод» включает свет, когда входит в комнату первый раз. Далее, если один из обычных узников входит и видит, что свет горит, он выключает лампу и в дальнейшем выключателя не касается. Через какое-то время счетовод снова будет вызван. Он опять включит лампу и т. д. В определённый момент счетовод выяснит, что лампу выключали ровно 99 раз. Тогда он будет точно знать, что все уже побывали в комнате.