100 заключенных застряли в тюрьме в одиночных камерах. Однажды надзирателю тюрьмы стало скучно, и он предложил им вызов. Он будет помещать одного заключенного в день, выбранного наугад (заключенного можно выбрать несколько раз), в специальную комнату с лампочкой и выключателем, который управляет лампочкой. Другие заключенные не могут видеть лампочку и управлять ею. Заключенный в специальной комнате может либо:
- включить лампочку,
- либо выключить лампочку,
- либо ничего не делать.
В любой день заключенные могут остановить этот процесс и сказать: "каждый заключенный был в специальной комнате хотя бы один раз”. Если это окажется правдой, все заключенные будут освобождены. Если это ложь, то все заключенные будут казнены. Заключенным дается некоторое время для обсуждения и выработки решения.
Какое решение им гарантировало свободу?
Ответ:
Поскольку это единственный способ выбраться из этой тюрьмы, они решают работать вместе и составить план. Они выбирают одного заключенного Колю, проще сказать, в качестве счетчика.
Каждый раз, когда выбирается любой заключенный, кроме Коли, они следуют этим шагам.
Если они никогда раньше не включали лампочку и лампочка выключена, они включают ее. Если нет, они ничего не делают. Теперь, если Коля выбран и лампочка уже включена, он добавляет одну к своему счету и выключает лампочку. Если лампочка выключена, он просто сидит и не чего не делает. В тот день, когда его счет достигает 99, он звонит начальнику тюрьмы и говорит ему, что “каждый заключенный был в специальной комнате по крайней мере один раз”.
Так как же работает это решение? Каждый раз, когда заключенный входит в комнату первым, он включает лампочку, если она выключена. Таким образом, каждый заключенный включает лампочку только один раз. Когда Коля входит и видит, что лампочка горит, он знает, что в комнату вошел один новый заключенный, поэтому он добавляет один к своему счету. Поэтому, когда его счетчик достигает 99, он знает, что все остальные были в специальной комнате, и, очевидно, он был в специальной комнате.