Комбинаторика на ММО: графы, турниры, логика, конструктивы

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

Когда число посчитанных узников становится равным “счётчик” говорит, что все узники уже побывали в комнате.

Действительно, каждый узник, кроме “счётчика”, включит свет в комнате не более одного раза. Когда “счётчик” насчитает он может быть уверен, что все остальные узники уже побывали в комнате хотя бы раз, кроме того он сам уже побывал в комнате. Получается, что к этому моменту все узники заведомо побывали в комнате хоть раз.

Остаётся доказать, что каждый из узников включит свет. Предположим, что это не так — свет будет включён менее раз. Тогда, начиная с некоторого дня свет включаться не будет. Так как никакой заход в комнату не будет для счётчика последним, он побывает в комнате после этого дня (например, на -й день, Если свет при этом горел, он его выключит. Значит, начнная с ()-го дня свет будет всё время выключен. Рассмотрим узника, который свет ещё ни разу не зажигал. Так как и для него никакой заход в комнату не последний, он побывает в комнате после -го дня. Но тогда он должен включить свет — противоречне.