Задачката е добра и аз доста се позанимавах с нея, но в един момент се отказах, защото не мога да напрвя оценка на очаквания период (може би Недев ще помогне тук)

Излагам по-долу първоначалните си разсъждения

Понеже един затворник трябва да вземе решението дали да каже, че всички са минали през стаята, то той трябва да е с нещо по-важен от другите. На пръв поглед всички от тях са равноправни заради случайния принцип на избиране....Кое ще направи някой уникален?!
Затворниците предварително знаят от кой ден ще започне "играта" . Тогава има един "специален" затворник и той е точно този, който ще има честта да влезе за първи път в стаята. Всички останали вече не са интересни и наистиа са равноправни.
Е, щом този затворник е специален, то той и би трябвало да вземе решението....

След това горе-долу е лесно.
Той светва лампата.
От тук на тататък той и само той има право да светва лампата.
Другите затворници ще се водят от следния принцип - ако лампата е светната, всеки затворник ще има право САМО ЕДИН ПЪТ да я загася. Т.е влиза обикновен затворник в стаята (той знае че е обикновен, защото не е бил първи)- вариантите са:
1. Лампата е загасена - той не прави нищо - оставя я загасена
2. Лампата е светната и той до сега не я е гасил - гаси я
3. Лампата е светната и той в някое предишно посещение вече е имал честа да я изгаси - сега не прави нищо - оставя си я светната

Специалния затворник (той знае, че е такъв) действа по следния принцип-
1. Лампата е загасена - той я светва
2. Лампата е светната - той си бърка в носа и не прави нищо
3. Брои
Като преброи че е светнал лампата 100 пъти - вече е сигурно че всичките 100 затворника са минали през стаята (някои по няколко пъти)


По груби сметки, без да съм специалист, това ще отнеме около 27-8 години, което е поносим период. Имам чуството, обаче, че този период може доста да се съкрати....

Редактирано от rovado на 11.10.05 18:54.