Казнить нельзя помиловать

В общей камере сидело 100 заключённых. Однажды к ним пришёл надзиратель и сказал: "Завтра я разведу вас по отдельным камерам так, чтобы вы не могли переговариваться. Затем я начну водить вас по одному в одну камеру, в которой будет только лампочка и выключатель. Единственное, что может сделать каждый заключённый - включить или выключить лампочку. Я выключатель трогать не буду. Выбирать кто пойдёт следующим я буду случайным образом, могу отвести несколько раз одного и того же. Кроме того, никто не будет знать, сколько раз заключённых водили в камеру до него и горела ли лампочка изначально или нет. Как только кто-то скажет, что в камере побывали уже все 100, я вас отпущу, если он ошибётся, казню."

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

Ответ: Заключённые договариваются, что 99 из них только выключают свет, а сотый - только включает. Причём те, которые выключают, выключают только по два раза, а после этого не трогают выключатель (Естественно, выключение считается, если свет горел, а его выключили. Если свет не горел и его оставили не горящим, то это выключением не считается. То же с включением). Тот, кот включает свет считает каждое своё включение. Как только он насчитывает 198 включений, он говорит, что все зеки уже были. Причём, если он заходя первый раз в эту камеру, видит включённый свет, ему достаточно насчитать только 197 включений. Между включениями света сотым заключённым каждый раз выключить свет может только один человек, все остальные, сколько бы их ни было оставляют свет негорящим и выключение не считают. Поскольку каждый заключённый выключает свет не больше двух раз общее число выключений будет не больше 198. В первый раз, заходя в камеру, включающий, если видит выключенный свет, не знает, был ли он выключен кем-то из зеков или был выключен изначально, зато все последующие разы он точно знает, что свет выключал кто-то из заключённых. Следовательно, когда он в 198 раз включает свет, он точно знает, что другие заключённые выключали свет как минимум 197 раз, причём каждый из них - не больше двух раз, следовательно, каждый из них был в этой камере по крайней мере 1 раз, а 98 - даже по 2 раза, как минимум.

- (наведите курсор)

Зеркало