Какъв Боян аз не съм добре. :) Тъкмо ще отбележа следното: Когато имаме 2 канала за предаване на информация можем да броим до четири, но нещо друго качествено различно: можем да броим в поредица (без повторения) като за всеки следващ слот да имаме възможност да отделим колкото си искаме (нарастващ) брой опита. Можем да използваме четири сигнала за да организираме тази система, и от тези четири дори остава един сигнал за да обозначи "1 човек преброен в аванс". Така могат да се преброят доста хора за малък брой дни.

ре вече е отговорил в едно изречение, но все пак и аз да си напиша:
100% сигурност си я имаш.
Не се иска гаранция, че в първият етап всички обикновени са минали(то даже само минаването им не върши работа - трябва и да са преброени). И да са и да не са преброени фаза2 си започва. Ако са преброени чудесно, ако не са за това си има зацикляне на фазите с по 300 дена. Когато успеят да се преброят тогава. То и резултатите от симулацията показват от 2300 до 8234(това разбира се горна граница няма, но само веднъж видях нещо към 10 000 и нещо) дена. Щом има резултати над 3500(2000+1500), то явно, че са минавали няколко пъти през фаза1 и фаза2.

С един преброител(без помощници) в 2 бита информация може се съдържа(всъшност това е една от оптимизациите на ре, коят е приложима тука):
1)вече е избран преброител
2)още не е избран преброител
Който влезе първи за втори път става преброител. Тези, които са влизали докато е било "още не е избран преброител" се считат за преброени и след избирането на преброител нищо не правят.
Разбира се за тази фаза - "избиране на преброител" трябва да се отдели време(и всеки да знае предварително колко е тази фаза): повече от 100 дена очевидно е безмислено, а дали да е 100 дена или по-малко е въпрос на калкулации.

Относно оптимизации на йерархичният модел на преброяване виж какво е писал ре. С включването и на лидера да брои обикновените затворници през първата фаза намалява средното време при мене с още 100 дена и се стига до към 3600. Другата оптимизация за избирането на лидер динамично не съм я пробвал, но той твърди, че се сваля до 3500.

Разбира се си прав, че за да са възможни оптимизациите трябва всеки да е наясно в кой пореден ден излиза. Относно всеки ден да изкарват точно по един затворник - условие 3 ми се струва, че е гарант за това.

Аха, значи имаш предвид вече "изгорели" стотачки да се доизкарват и тогава да се започва нова. Колко ли време ще отнеме всичко това?

Оптимизирането с 1 преброител. Казваш, който влезе първи 2 пъти става преброител. Ок, той ще знае че е преброител, но как другите след него да разберат, че не са преброители. След него пак може да влезе някой за втори път на тъмно и да се помисли за преброител.

След като е избран преброител, то до края на фазата "избиране на преброител" лампичката ще казва: "вече е избран преброител". Така, че ще знаят.
Ако до края на фазата никой не е влязъл за втори път лампичката ще казва: "още не е избран преброител" и този който влиза в последният ден на тази фаза става преброител.

Да бе:) Малко след като написах предното се сетих, че имат период за избор на преброител. Разсеял съм се нещо напоследък

За 4-ма: Предполагам 12 1/3 го получаваш като третият влязал(не третият ден, а третия различен затворник, който влиза за първи път) обявава край на играта. Но краят може да се обяви от първият и/или вторият, ако те са влезли след третият и преди 4-тият.
Тактиката е когато влизаш за първи път сменяш осветлението - така при първо влизане всеки знае четността си на влизане(тъй като 3-тият знае, че не е първи, то явно разбира, че е трети; вторият разбира, че е втори само ако е влязал 2-рият или 3-тият ден(иначе не знае дали не е 4-ти)). При всяко следващо влизане, ако лампата е различна от това дето е оставил последният път, то разбира, че поне още някой е влизал. Първият също така при следващато си не последователно влизане, ако завари същото осветление значи, че са минали 2-ма(т.е. влиза първите к дена и е оставил светнато, ако не е влязал на к+1 ден, то явно, че е влизал поне още един затворник, но ако когато влезе за втори път(първите к последователни влизания може да ги броиме за един път) и ако пак е светнато, то явно, че са минали още 2-ма след него(той вече е преброил 3-ма). След това ако види загасена лампа може да обяви край на играта). Вторият и четвъртият не знаят кои са, но могат да предполагат, че са втори(т.е. ще знаят поне двама са минали). При следваща смяна на осветлението, която забележат ще увеличават с 1-чка броят на хората, които са минали със сигурност (разбира се такова нещо може да се случи само на вторият, тъй като четвъртият е последният, който променя осветлението).
Би трябвало да може да се докаже, че очакването по горните съображния е към 10 7/9(но дали е оптимално не знам)
10 милиона симулации дават това:
The average is:10.7763614
min is:5
max is:62
array_10:7
array_50:10
array_80:13
array_85:14
array_90:16
array_95:18
array_99:24

А че няма как четвъртият винаги да знае, че е четвърти може да се докаже лесно:
Ако допуснеме, че винаги може да го знае, то ще имаме една функция f(x)->{0,1} за всяко х>=3, по която затворник като влезе за първият път в ден х ще знае дали е 4-ти или не. Това означава, че влезлият в ден х винаги ще знае, в какво състояние да остави лампата. Но ако влезе за първи път след третият ден и не е четвърти(така му показва функцията), то той няма да знае дали е 3-ти или 2-ри. Ако е 3-ти трябва да остави лампата в състояние f(x+1), ако е втори в противопложното състояние.

Така е, идеята ми беше третият да вика "ура". После се сетих, че и другите могат да му помагат, но не се сетих, че "Първият също така при следващато си не последователно влизане, ако завари същото осветление значи, че са минали 2-ма" и затова успях да сляза само до 11.15 дни. Твоите 10.78 са може би възможният минимум.

За петима стигнах до идеята, че май ще е най-добре да брои влезлият в четвъртия ден. Понеже съществува неопределеност, колко са минали преди него, той ще може да сигнализира на влезлия през петия ден, че му преотстъпва преброителската роля, а влезлите през първите три дни ще помагат при нужда да се разреши неопределеността. Алгоритъмът се получи доста заплетен и доста неефективен - не ми се удава да сляза под 20 дни. Ако успея да го доизчистя, ще пиша пак. Алгоритъмът с преброител от третия ден засега ми излиза мъничко по-бавен.

Вижте пък аз какво измислих. Накратко идеята е следната:
Броят всички затворници. При първото си влизане в стаята всеки брои себе си за 1 човек. При следващите влизания затворниците си прехвърлят бройки. Някой затворник дава от своите бройки и сигнализира с лампата. Друг, влязъл след него, взема бройките му и ги добавя към своите, така че сумата на бройките на всички затворници остава равна на броя на влезлите. Който пръв събере 100, вика уво.
Сега подробностите:
Календарът се разделя на 7 фази: Ф0,Ф1,...,Ф6, които са с предварително зададени продължителности и в предварително определен ред. Всеки затворник поддържа личен брояч, като в началото броячите на всички са 0 с изключение на един (няма значение кой), който е 28 (за да се брои не до 100, а до 2^7=128). Затворниците записват броячите си в двоична бройна система. В която и фаза да влезе даден затворник за първи път в стаята, той увеличава брояча си с 1. Освен това всеки път, когато затворникът е в стаята, той се старае да се отърве от някоя по-младша единица в брояча си. Разрядът се избира според фазата: Ф0 съответства на бит 0 в брояча, Ф1 - на бит 1 и т.н. Ако например затворникът влезе в стаята през Ф3, той гледа, дали броячът му съдържа 1 в бит 3 (разрядът на осмиците).
Ако съответният бит е 0, затворникът не прави нищо.
Ако съответният бит е 1 и лампата не свети, затворникът я запалва и намалява брояча си (с 8 в случая), така че съответстващия на фазата бит да се нулира.
Ако съответният бит е 1 и лампата свети, затворникът я гаси и увеличава брояча си (с 8 в случая), при което въпросния бит пак се нулира.
Ако затворникът влезе в първия ден от някоя фаза и лампата свети, той безусловно увеличава брояча си с числото, съответстващо на предходната фаза.
Който пръв получи 128, обявява освобождаването.
Хубавото на алгоритъма е, че изисква всички да влязат по не повече от 7 пъти последователно (при йерархията на преброители числото е около 20). Лошото е, че трябва да се влиза в определена фаза.
Много е трудно да се направи оптимизация на разделянето по фази. Поиграх си малко на ръка, но тази работа явно изисква нещо повече. Най-добрият ми резултат е за следния график: Ф0=420,Ф1=270,Ф2=150,
Ф0=420,Ф1=470,Ф2=500,Ф3=560,Ф4=520,Ф5=510,Ф6=510,
Ф0=300,Ф1=350,Ф2=400,Ф3=510,Ф4=510,Ф5=510,Ф6=510,
и оттук нататък се редуват от Ф0 до Ф6, всички по 510 дни. Получават се средно 4680 дни до освобождаването - повече от решението на Поназнайващ, но предполагам, че една добра оптимизация би могла да намали съществено това време. Най-голяма е вероятността да излязат на 4330-я ден.

ако съм те разбрал правилно, то струва ми се, че това е еквивалентно на йерархичен модел със 7 нива и преброяване до 2 на всяко ниво. аз опитах същото и имах подобно 'закръгляване' до 128 и резултатът ми беше горе долу в 4 хилядите и нещо. броенето до 2 е по-особено, защото не е необходимо да се фиксират предварително преброителите - просто всеки който получи сигнал се счита за преброител и преминава в следващото ниво. така се спестява малко време от втората част на очакването (когато чакаме преброител). в оптималната ситуация (когато всички периоди си завършват на време) са необходими:

100(1+1/2+...+1/100) +
100(1+1/2+...+1/50) +
100(1+1/2+...+1/25) +
100(1+1/2+...+1/13) +
100(1+1/2+...+1/7) +
100(1+1/2+...+1/4) +
100(1+1/2) = 2285.9 дни

но пък ако някой период не завърши на време, всеки допълнителен ден се наказва 7-кратно (ти ги наказваш от самото начало, разглеждайки периодите едновременно). затова е трудно да се постигне добър резултат и изобщо да се нагласят нещата.

ако не знаете как да ги нагласите, и ако имате време за играчка това е генетичен алгоритъм - тези които не знаят да не се плашат - много е просто - имате само периодите, и давате да се изменят леко (мутират) и да се комбинират (взимате средното на двата периода). най-добирте стратегии "оцеляват" и т.н.