Давно я не задавал тут старых классических задачек.
Вот сегодня мне попалась задачка. Она не очень сложная, но интересная.
Есть комната, в ней есть лампочка, и выключатель к ней. Есть N узников. Все узники сидят в разных изолированных комнатах, и не видят друг друга -- как следствие не могут общаться или делать каких-то выводов о происходящем. Время от времени охранники выбирают одного из узников, и помещают его в комнату на ночь. На утро его выпускают. Он, конечно, видит, в каком состоянии лампочка, когда он входит, и, уходя, он может ее оставить в любом состоянии. Лампочка не перегорает, и охранники ее состояние не меняют.
Задача -- выработать узникам такую стратегию (допустим, что перед началом всей этой истоии, им дан один вечер собраться вместе и обсудить ее), при которой один из них в какой-то момент времени сможет сказать с вероятность 100%, что каждый из них уже побывал в этой комнате хотя бы раз.
У задачи два варианта -- в одном в начале лампочка выключена, во втором в случайном состоянии.
Без этого условия нет шансов. Кстати, посмотрите мой второй пост.
> чтобы каждый чувак побывал в ней в итоге бесконечное количество раз (точнее, если в какой-то момент времени чувак вошел, то существует в будущем такие моменты, когда войдут все остальные)
Одно и то же (равносильное утверждение - уточнение).
Если речь о том, что каждый побывает бесконечно много раз, то мы не можем говорить о вероятности здесь, ибо в условии не задано вероятностное пространство.
Если считать, что равновероятно выбирают любого из них, утверждение, что каждый с вероятностью 1 посетит комнату больше, чем наперед заданное X, раз, очевидно.
Для решивших.
То же самое, только ВСЕ участники должны сказать, что каждый был хотя бы один раз. Они могут сделать это не одновременно. Утверждаемое должно быть обязательно верно. Остальные правила не меняются (тот факт, что участник сказал ответ, не отличает его от других).