Водной тюрме на международный день зэков устроили конкурс-игру. в игре берут участие все заключенные и в случае выиграша администрация обещает всех их выпустить. вот в чем состоит игра: всех зэков разводят отдельно по разным карцерам. потом какого-то одного из заключенных выпускают и ведут в специальный карцер с лампочкой. никто из заключенных не знает и не может подсмотреть кого именно в тот карцер ведут. в специальном карцере есть 1 лампочка и зэк имеет право включить/выключить/оставить без изменений лампочку. потом его снова закрывают в его карцере и берут любого другого заключенного (это может быть и тот самый). так игра продолжается целый день. зэки выиграют если какой-то из заключенных вийдет из специального карцера и скажет "тут уже были все заключенные" и это будет правдой, иначе, если это неправда, игра заканчивается. перед началом игры заключенные могут обговорить между собой стратегию игры, но во время игры никто ни с кем не может общаться. в начале игры состояние лампочки неизвестно. полностью на логику, не имеет никаких приколов типа оставить какой-то знак в спецкарцере, или на ощупь определить сколько работает зэкам выбраться из тюрмы!
решаема, причем скорее всего даже не одним алгоритмом, но другое дело насколько они применимы в реальной жизни ) т.к. мат. ожидание может быть нуу большим.
например:
каждый чел которого приводят включает лампочку, если она не горит, притом только один раз, сколько бы его не приводили.
один из зеков выключает каждый раз лампочку когда его приводят и считает.
в конечно итоге он выключит лампочку столько раз, сколько всего человек учавствует в игре.
возможно но не точно