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