Разделы 
Дополнительно
Задача по математике - 3391
2019-06-03 
В тюрьму поместили 100 узников. Надзиратель сказал им:
«Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.
Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ - скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут, - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним.»
Придумайте стратегию, гарантирующую узникам освобождение.
Решение:
Приведем одну из возможных стратегий узников. Выберем одного из узников (будем называть его «счетчиком», а остальных узников - «обычными»). Он будет считать узников, которые посетили комнату, следующим образом. Вначале число подсчитанных узников равно 0. Далее, если, приходя в комнату, он обнаруживает, что свет включен, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из «обычных» узников действуетпо такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, «счетчик» говорит, что все узники уже побывали в комнате.
Докажем, что эта стратегия гарантирует узникам освобождение. В самом деле, действуя согласно этой стратегии, каждый узник, кроме «счетчика», включит свет в комнате не более одного раза, а «счетчик» вообще не включает свет. Если «счетчик» насчитает 99, значит каждый из оставшихся узников побывал в комнате хотя бы раз. И «счетчик» там, конечно, уже был.
Остается доказать, что «счетчик» в какой-то момент «досчитает» до 99, т. е. что каждый из 99 узников включит свет. Предположим, что это не так - свет будет включен менее 99 раз, т. е., досчитав до некоторого числа $m < 99$, «счетчик» выключит свет, и больше свет никогда зажжен не будет (иначе, зайдя в комнату после следующего включения света, «счетчик» досчитает до $m +1$). Так как «обычных» узников больше m, то найдется «обычный» узник, который свет никогда не зажигал. По условию он окажется в комнате и после указанного выше момента. При этом, следуя указанной стратегии, он должен будет включить свет. Противоречие.
В тюрьму поместили 100 узников. Надзиратель сказал им:
«Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.
Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ - скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут, - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним.»
Придумайте стратегию, гарантирующую узникам освобождение.
Решение:
Приведем одну из возможных стратегий узников. Выберем одного из узников (будем называть его «счетчиком», а остальных узников - «обычными»). Он будет считать узников, которые посетили комнату, следующим образом. Вначале число подсчитанных узников равно 0. Далее, если, приходя в комнату, он обнаруживает, что свет включен, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из «обычных» узников действуетпо такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, «счетчик» говорит, что все узники уже побывали в комнате.
Докажем, что эта стратегия гарантирует узникам освобождение. В самом деле, действуя согласно этой стратегии, каждый узник, кроме «счетчика», включит свет в комнате не более одного раза, а «счетчик» вообще не включает свет. Если «счетчик» насчитает 99, значит каждый из оставшихся узников побывал в комнате хотя бы раз. И «счетчик» там, конечно, уже был.
Остается доказать, что «счетчик» в какой-то момент «досчитает» до 99, т. е. что каждый из 99 узников включит свет. Предположим, что это не так - свет будет включен менее 99 раз, т. е., досчитав до некоторого числа $m < 99$, «счетчик» выключит свет, и больше свет никогда зажжен не будет (иначе, зайдя в комнату после следующего включения света, «счетчик» досчитает до $m +1$). Так как «обычных» узников больше m, то найдется «обычный» узник, который свет никогда не зажигал. По условию он окажется в комнате и после указанного выше момента. При этом, следуя указанной стратегии, он должен будет включить свет. Противоречие.
