Ето една задачка, която ме мъчи от доста време. Извинявам се предварително ако вече е пускана тук. Тогава просто ми дайте линк към темата.

На шефа на един затвор със 100 затворника-смъртници му се родил син. В изблик на радост той решил да даде шанс за амнистия на всички затворници. Официално обявил, че от следващия ден правилата в затвора се променят по следният начин:

1. Временно се прекратяват изпълненията на смъртните присъди
2. Всички килии се звукоизолират и прозорците им се зазидват
3. Всеки ден килията си ще има възможност да напусне само един единствен случйно избран затворник и никой друг.
4. Разходката си той ще може да направи в специално създадена за целта вътрешна звукоизолирана стая в която има само една единствена крушка, която всеки от затворниците може да си светка и загасва колкото си иска.
5. Никой друг (директор, пазачи..) освен затворника, който в момента е в стаята няма право да пипа крушката.
6. Крушката е "железарка" и няма никакви шансове да изгори или се повреди в следващите 100-150 години.
7. Всеки един затворник, който е "поканен" на разходка в стаята ще има възможността да освободи всички останали. Ако той е сигурен и заяви, че всички останали негови колеги вече са минали през тази стая и това е вярно, то свободата е тяхна (на всичките 100). Ако обаче той направи такова изявление и то не е вярно, всички смъртни присъди ще бъдат изпълнени веднага.
8. Само за протокола - всички възможности за каквато и да комуникация м/у затворниците, както и всякакви пишещи, цапащи и т.н предмети са отнети.
9. Затворниците ще прекарат заедно ноща преди началото на играта на двора на затвора, за да могат нещата да се приготвят.

Въпросът е: каква тактика да възприемат затворниците с цел 100% им освобождаване?
И по-трудния въпрос - каква е очакваната продължителност на играта?

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




NE SUTOR ULTRA CREPIDAM

Условието, доколкото вярно съм преценил, не изисква спазването на точния момент, когато всички вече са минали през стаята.Може и много по-късно. При това положение трябва да разделят бъдещия си престой на по 100 дни, които да започват със угасена лампа напр. Ако в тия 100 дни някой повтори влизане запалва лампата и тая стотачка "изгаря". Все някога ще се случат 100 дни без повторение и последният влязъл като види угасена лампа ще ги освободи. Тъй като това решение ги обрича на доста дълъг престой потърсете по-добро, че да им го съкратите.

И, как ще се информират, че започват нова "стотачка"?

Има идея в това, но как ще обменят информация кой кой номер е бил видял, че е бил вътре. Ако трябва един човек да чака да влиза в различни по модул 100 дни и да се надява, че точно определен човек е бил преди него....не ми стигат силиците за да сметна колко години ще отнеме това

Ами всеки брои за себе си дните от 1 до 100 и почва наново от 1(това би трябвало да уговорят в ноща преди играта). Да се номерират няма смисъл, тъй като разполагат само с един бит информация, т.е. дали дадено събитие се е случило или не - в случая дали някой е влязъл два пъти през поредната "стотачка". Според моята логика това е начинът за 100 човека, 100 дни и 100% сигурност, но може и да греша.

има. Ако затворник с номер 1 влезе 1-вия ден, 2-втория и т.н луд късмет. Вероятността това да се случи е 100^(-100), Да го наречем "опит". Един опит продължава 100 дена и вероятността да е успешен е 100^(-100). Ако някой затворник (случайно) не влезе в деня на неговия номер - угася лампата и чакаме другите 100 дена. И когато затворник номер 100 влезе в ден 100(по модул разбира се) и види ламБата да свети вика бинго. Ако достатъчно дълго опитват все някога ще успеят, но по -вероятно е да са измрели до тогава. А и крушката ще е изгоряла - каза 150 години, ама това ще продължи бая по-дълго. Не знам, не става и по индукция да се тръгне - от 2-ма, 3-ма и т.н, щото няма период, за който може да се каже със сигурност че н човека ще са влезли. Почвам да си мисля че няма начин за що годе разумен период да се достигне 100% сигурност, дано да греша. Надявам се да чуя хубаво решение и да не се окаже глупост от рода на въжетата и дупката, или пък да кажеш след месец: сори, те ламБите били 2. Змея беше изкарал една формула от друга задача, според която всички ще са влезли средно след
100*(1+1/2+1/3+1/4+......1/100) дена или къде 590 дена. Та ако аз бях в затвора щях да предложа след 3 години да викаме и да излизаме и да не си играем с ламбите

Имам няколко идеи, но първо да се опитам да поразвия твоята.
Играем по следния начин:
обявяваме първите х дни да "рожден ден" на номер 1, следващите х - за рожден ден на втория и т.н.
Ако някой влезе по време на свой рожден ден, светва лампата ; до края на х-те дни лампата остава светната и така всички влезли след него разбират че той вече е бил вътре. Когато някой разбере че всички номера вече са били вътре, вика УРА. Остава да сметнем коя е оптималната стойност на х (твоя вариант е х=1). По съвсем груби сметки, ако х=476 дни, след 47600 дни (само 130 години) с вероятност 50% все някой ще знае че всички са били вътре. Не е кой знае какво, но е доста по-добре от твойто, за което трябват 3025300 дни, или към 8288 години.

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

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

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

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

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


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

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

Това за, което се сещам ще ги извади след около 5500 дена.
1) Избират си един лидер, който ще им обяви свободата - той ще преброява колко със сигурност са влезли.
2) Не лидерите нямат право да гасят лампата. Всеки от тях я светва само веднъж при първа възможност(ако първоначално лампата е светната, то първият, който влезе ако не е лидер се счита, че я светнал, а ако е лидер я гаси без да го включва в бройката).
3) Лидерът само гаси лампата и като я угаси за 99 път им обявява свободата.

Очакваната продължителност я разделям на 2 части:
1) светлите дни - 99 пъти ще бъде светната лампата и след това лидерът трябва да влезе - средно след около 50 дена - та до тука до към 5000 дена
2) тъмните дни - при изгасена лампа да влезе някой дето не е изброен, че да я светне - първоначално ще е доста бързо(докато има по-малко от 50 неизброени се очаква за по-малко от 2 дена) докато се стигне накрая до към 17, 25, 50 очаквани дена за последните - май общо някъде е до към 400-500 дена
Хм, май по-добре да обърнат стратегията, че да поспестят малко ток
Ако има някой по-нетърпелив може да се опита след 3-тата година да ги освободи на своя глава - вероятността за успех е над 99.5%.

Решениетона Zaphod, ако не се лъжа е от порядъка на 100^3(всеки ще влиза в хубав за него ден веднъж на 10 000 реални дена(всеки 100-тeн ден е хубав за него - а вероятността да влезе е 1 към 100) - т.е. веднъж на 27 години за да влезе и на следващият ден някой да забележи, че той е влязал - докато има един който да знае, че всички останали 99 са минали май ще минат към 1000-3000 години)

Решението на V-6O за стотачките отива към очаквани 10^39 години(вероятността в определна стотачка всички да минат е 100^100/100!).

Nedev е дал към 130 години - не е зле, но нямат надежда за по-малко от 129 години да се оправят

Това беше моя реплика, трябваше аз да я кажа

Доста ти е крива сметката : първо, лидерът влиза средно веднъж на 100 а не на 50 дни. Значи, КАТО МИНИМУМ ще трябва да влезе 99 пъти, демек средно 9900 дни. Трябва и да споменем, че към края бая често ще му се случва да влезе и да намери ламбата загасена - никой непреброен не е влизал между последните му 2 влизания. Но метода си го бива, а оценката на Ровадо ми изглежда горе-долу коректна. Сега смятам.

Много лесно се смята средното време, всъщност: За да влезе някой от редовите затворници са нужни средно 100/99 дни, после за да влезе лидера - средно 100 дни, после средно 100/98 дни за да влезе неотбелязан редови, после 100 за да влезе шефа, и т.н. 100 дни за да влезе последния неотбелязан плюс 100 дни за шефа. Сумарно 99*100+100*(1/99+...+1/2+1)=10418 дни или 28.5 години средно. Най-добре шефа да бъде определен предварително, а не като този който влезе пръв, щото така се губи 1 ден, ма при тия мащаби тва едва ли е от значение.

Прав си - намазал съм сметките, а твойте изглеждат ок.
13.5 години в затвора не са малко предполагам

Да - тези сметки изглеждат коректно. Аз разсъждавах по- просто - лидерът трябва да влезе сумарно 100 пъти, което значи, че и всеки от затворниците трябва да влезе по 100 пъти- това прави 100*100 = 10 000 дни или 27,3...години

Това решение сравнително бързо се открива. Въпросът е има ли по-къс очакван период и ако да как?
Това е въпросът, който ме тормози от 1-2 месеца. Имам идеи, но ще изчакам да видя как ще тръгне дискусията тук. Лошото е, че дори си нямам и на идея как да сметна очаквания период.

Между другото тази задачка я пусна някакво хлапе в друг форум и избяга с развята коса, когато стана въпрос за решения. Не съм се ровил из чуждоезични сайтове за нея, защото все още ми е интересна. Ще се радвам ако и тук се измисли нещо

Редактирано от rovado на 11.10.05 20:47.

мисля че времето на "полуизход" е 100 *(100^100)/100! дена, което е 1.07Е44, но все пак ми изглежда по-бързо от моето.




NE SUTOR ULTRA CREPIDAM

vremeto se razdelia na periodi ot 100 dena (ili 3 meseca za udobstvo)
na vseki period ot vreme saotvetstva edin zatvornik (kato nomerata im sa izvestni na vsichki)
na 101 period saotvetstva 1via zatvornik .e. povtariat se csiklichno
vav vseki period samo choveka koito mu saotvetsta svetva lampata, a ostanalite ia gasiat.
iskluchenie ot poslednoto e, che kogato edin zatvornik znae, che tozi, chiyto period e sega, e bil veche v staichkata, to toi sashto ia svetva.
izkliuchenieto shte pomogne za ikonomia na vreme.

Май успях да поизмисля някои неща. Разделяме ги смъртниците на 90 обикновени, 9 специални и един лидер.
Фаза 1 - първите 2000 дена обикновените светват по веднъж лампата(ако е светло или вече веднъж са светвали, то нищо не правят). Специалните гасят точно по 10 пъти. Лидерът нищо не прави
Фаза 2 - следващите 1500 дена обикновените нищо не правят, специалистите светват по веднъж, ако в предишната фаза са изгасили 10 пъти, иначе нищо не правят. Лидерът гаси - ако изгаси 9 пъти вика УРА и всички се прибират у тях.
Следва редуване на фазите с продължителнсот примерно 300 дена.
В последният ден на фаза, ако лампата свети се гаси, като ако този дето я изгасил не би трябвало да прави, то следващият път като се появи тази фаза светва веднъж(в повече). Ако не свети - нищо не прави.

Очакването на 90-те обикновени е да им трябва 100(1/90 + 1/89 + ... + 1/2 + 1)=508 всеки да успее да светне лампа(това са точно дни когато лампата е изгасена и се очаква да я светнат)
На 10-те специални да изгасят тези лампи е повече от 90*100/9=1000 - ще е повече защото за последните 20 тина гасения няма да умножваме по 100/9, а нещо по голямо 100/8 до към 100/1 последният път(евентуално последните 2 може да се случи).

Аналогично се получава 293 дена 9 те специални да светнат лампа и 900 дена лидера да ги изгаси.

Струва ми се, че тука очакването като цяло ще слезе доста под 10000, но и аз не знам колко точно ще отиде.(след първо минаване на всяка от фазите би трябвало всички да са се изредили, ама може някой да остане и стават мизерии)

Мислех за разделяне на повече гурпи с повече, но по кратки фази примерно 80 16 4 1 - всеки брои от предишната група, но става още по-кофти да предвидиш очакването.

Здрасти ГАЗ!Ако се изсереш на клавиатурата 6те ти кажа отговора......ГъъъъъъъЗ .....Радвам се да те видя онлайн....бе6е ми приятно неазивисимо какво 6те се пита6 как.....АНгли4анина.......дето пргограмира..ей..там....Еййййййй........... Бат Тони! Поздрави Алек...........р

Ама, чакай сега...

> 3. Всеки ден килията си ще има възможност да напусне само един единствен > случйно избран затворник и никой друг.

Това какво точно означава? Означава ли, че всеки ден задължително излиза един - единствен затворник и влиза в стаята с крушката, или този случайно избран затворник може да избере дали иска да излезне или не? А, ако може да избира и избере да излезне, може ли да избере дали да влезне в стаята с крушката или не може?
...
А може ли един и същ затворник да бъде избран да излезне в два различни дни или веднъж избран затворникът вече не може да бъде избиран?

Виж това след като се предадеш или си сигурен, че си намерил оптималното решение:

http://www.cut-the-knot.org/htdocs/dcforum/DCForumID4/634.shtml

Спретнах една програмка, която симулира по 10 000 пъти дадена стратегия:
Ако има един лидер, който преброява останалите 99 затворника:
The average is:10427
min is:7097
max is:14861
array_10:9179
array_50:10383
array_80:11260
array_85:11471
array_90:11750
array_95:12149
array_99:12893

Стратегия 1 9 90 с първа фаза 2000, а втора 1500 и след това при следващите повтаряния по 300 дена:
The average is:3855
min is:2300
max is:8234
array_10:2910
array_50:3896
array_80:4550
array_85:4622
array_90:5058
array_95:5229
array_99:5893


Пак 1 9 90, но с първа фаза 2250, а втора 1500:
The average is:3736
min is:2546
max is:8297
array_10:3078
array_50:3502
array_80:4243
array_85:4333
array_90:4784
array_95:4948
array_99:5973


Едни от най-добрите резултати се получават при 1 11 88 и съответно за фазите 2050 и 1850:
The average is:3713
min is:2500
max is:7910
array_10:3055
array_50:3509
array_80:4318
array_85:4402
array_90:4853
array_95:5021
array_99:5690


array_80:4318 означава, че 80% от симулациите са свършили до 4318 дена.
Повторенията на фазите навсякъде са ми 300 дена.
Ако не съм допуснал някъде грешка излиза, че могат да си направят стратегия с която ще излязат за по малко от 10 години с вероятност повече от 50%(а средното им ще бъде малко над 10 години).

Стратегия в която се вкарва още едно ниво ми се струва вече ще бъде по-зле - но не съм я симулирал.

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

Вероятността P да има все още невлизали в стаята с лампата затворници намалява експоненциално с времето (по-точно, асимптотично клони към това).
Точната вероятност за d-я ден при n затворници е
P = n^-d * [сума по k от 1 до n-1](-1)^(n+k+1)*[n над k]*k^d

Така рискът намалява с времето по следния начин:
под 10% на 683-я ден
под 1% на 916-я ден
под 0.1% на 1146-я ден
под 0.01% на 1375-я ден
под 0.001% на 1604-я ден
под 0.0001% на 1833-я ден
под 0.00001% на 2062-я ден

Вижда се, че така или иначе ще се чака средно 518.7 дни (1 година и 5 месеца), докато всички минат през стаята (дори ако затворниците имат не само лампа, а идеални комуникации), а после рискът намалява по 10 пъти на всеки 229 дни. Аз бих казал да изчакаме 4 години и после да си ходим...

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

ако никой не се е повторил, човекът на 20-ия ден става лидер. лампата е светната докато се стигне до повторение, а след това е загасена до 20-ия ден.

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

след 20-ия ден се процедира по другия алгоритъм.

тези две неща към решението на поназнайващ ми дадоха решение средно за 3500 дена.

друга забележка: намерете оптимална система за 3-ма затворника сред 97 ретранслатора. (слагам ги така за да не може да се използва знание за дните). излиза ми 283 дена средно. същото за 4,5,6 затворника...?

Mnoo si daleche che lidera triabva da vlezne sumarno 100 puti shtoto mezhdu 2 vlizaniia na lidera moe da ne e vlizal nito edin nov ... togava shte mu triabva da vlezne pone 101 puti ...
vizh che shte zagasi lampata 100 puti veche e viarno ma ne pomaga osobeno mnogo :)))

Join the dark side, and get a free cookie.

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

или като Доминиканската лотария :)

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

Аз се опитах да поумувам какво ще стане, ако затворниците са не 100, а по-малко: 2, 3, 4, 5 и т.н.

За двама решението е тривиално, защото лампата става излишна. Средното време за освобождаване е 3 дни.

За трима съществува оптимален алгоритъм от средно 5.5 дни. Той е оптимален, защото гарантира, че последният влязъл за пръв път при лампата затворник веднага да разбере това.

За четирима обаче не съществува такъв алгоритъм, при който математическото очакване за времето на процедурата да съвпада с математическото очакване за времето на извъртане на всички затворници през стаята (което е 8 1/3 дни). Струва ми се, че това би могло да се докаже, но не съм го доказвал. Имам алгоритъм за 12 1/3 дни средно, но даже не зная, дали е оптимален.

За петима става много сложно.

В задачата се иска 100% сигурност, такъв и е смисъла. Няма 100% гаранция, че обикновените ще минат за 2000 дена. Че да започва втори етап. Ако правиш компютърни симулации, избери си един юнак (или няколко),който изобщо не влиза. Коректно е програмата да върти вечно. Не става с повече от 1 преброител, не става и с помощници. Единствено оптимизиране е преброител да е този, който влезе на 3-ия ден. (Може с 1 бит да получи информация дали 1 или 2-ма човека са минали, ако самия той влезе и по-рано, може да си направи сметката). И то само при положение, че със сигурност ВСЕКИ ДЕН карат по един и знаят от кой ден почват.

Мисля, че няма принципен проблем да се направи алгоритъм с йерархично организирани преброители. Може периодите на преброяване на различните нива на йерархията да се разделят на календарен принцип. Това обаче е много неефективно, защото ако влезеш в грешен период, нито получаваш, нито предаваш полезна информация.

Повече ми допада идеята за някакъв по-симетричен и "демократичен" алгоритъм. Има според мен нещо много полезно в идеята на Nedev за рождените дни, в която приемниците на полезната информация са много.

Чудя се също, дали не може да се автоматизира (поне донякъде) търсенето на ефективен алгоритъм (поне за малък брой затворници). Очевидно могат да се генерират случайни алгоритми по метода на пълното изброяване и да се тестват по метода Монте Карло за правилност (частично поне) и ефективност. Не се сещам обаче как да се сведе до малък брой параметри описанието на паметта на затворниците за миналото.

Да кажем, алгоритъмът може формално да се опише като изображение на множеството на всички възможни състояния на затворника върху множеството на неговите действия. Състоянието на затворника трябва да внлючва:
- паметта му (минали влизания, броячи и пр.) - ????????
- датата
- завареното състояние на лампата
Действията на затворника са 3: оставя запалена лампа, оставя загасена лампа, обявява край.

Ако паметта може да се формализира с малък брой параметри, може да се действа и с груба сила.

Идеята на Боян може се видоизмени до броадкастинг, но пак няма да подобри много нещата. Ако в период i се очаква появяването на затворник i (който може да светне лампата), и ако той действително се появи, то всички, които излезнат в оставащите дни от периода, ще знаят, че i вече e минал през стаята. Тогава в период 100+i всеки един от тези последните също може да светне лампата. Проблемът отново е, че дори когато всеки е научил за появяването на даден затворник, периодът който му е бил отделен не може да бъде анулиран.

(към другия пост: и все пак за всяко n съществува някаква оптимална стратегия. откритите начини за предаване на информация засега не са толкова много: "импулсно броене", "броене в поредица", "броене във фиксиран период" - всички тези във възможно "йерархична организация/комбинация". съществува ли някакъв друг, качествено различен метод на броене?)

за палячо: накрая поназнайващ редува двете нива (период 300 дена).

Какъв Боян аз не съм добре. :) Тъкмо ще отбележа следното: Когато имаме 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-кратно (ти ги наказваш от самото начало, разглеждайки периодите едновременно). затова е трудно да се постигне добър резултат и изобщо да се нагласят нещата.

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

извинявай, не съм видял накрая - първото завъртане периодите са ти различни... значи и ти правиш същия номер.

Няма смисъл да правиш първо ф0,ф1,ф2 и после пак ф0,ф1,ф2,ф3,ф4,...., защото така надробяваш първите 3 фази без шанс да излезеш след тях. Т.е. нищо не печелиш с раздробяването, а може да загубиш - в първият ден на следваща фаза искаш не искаш прибираш каквото има - с повече накъсвания е по-вероятно това да се получава.

Също така първоначалната инициализация може да се подобри:
Вместо 99х1+1х29 - може да се ползва 28х2 +72х1(горе долу само това преконфигуриране сваля към 100 при по-долу подбраните числа за фазите)

Използвайки горните две неща и дълготрайност на фазите{750,755,690,625,560,500,480} след това зацикляне на 300 го докарах към под 4500.

The average is:4482.9462
min is:3881
max is:16859
array_10:3922
array_50:4020
array_80:4200
array_85:4339
array_90:6268
array_95:6446
array_99:10410

Дори и да има по-добър подбор на фазите под 4300 средно не ми се вярва да се докара. Може доста да се подобри array_50:4020 - някъде до към 3400(т.е. затворниците ако си падат оптмисти и не мислят за средното и най-лошото може да излязат към 2 години по-рано)

Между другото се бях сетил една подобна идея фазите вървят от ф0,ф1,ф2,ф3,ф4,ф5(няма ф6, защото 64 като събираш до 100 не върши работа),ф4,ф3,ф2,ф1,ф0 - като последното е докато някой събере 100, като дали да прибереш(гасиш) или не, дали да оставиш(светиш) или не, горе долу зависи колко имаш до момента. Докарах го до към 5000 средно, но си е доста зле.
Също така мислих и върху една малко хаос идея(всъшносто тя може да се гледа като обобщение на горните): Предварително си определят в кой ден колко си прибавяш ако загасиш. Като светваш вадиш от брояча си толкова колкото на следващият ден струва гасенето. Общо взето кофти резултати се получаваха - твърде много ненужни прехвърляния.

Прав си, раздробяването вреди. За инициализацията: мислех вместо от 28 да започна от 16+8+4, но на практика нямаше никаква разлика. За 14х2 хич не се сетих.

Все едно, явно този алгоритъм няма шанс да стане шампион. Незавършването както трябва на някоя от ранните фази се наказва твърде тежко, както посочи и ре.

Интересно, дали има начин теоретично да се даде оценка за средната продължителност на максимално ефективния алгоритъм?

В отговор на:

---

Интересно, дали има начин теоретично да се даде оценка за средната продължителност на максимално ефективния алгоритъм?

---

Редактирано от rovado на 22.10.05 12:15.

Все пак доста ми харесва този алгоритъм със 7-те периода с броене до 128 без определени преброители. Необходимо е само Ненулевите да влязат поне по веднъж във всеки период. И е горе-долу теоретично оценим. Ако един алгоритъм с твърдо зададен период за реализация N има вероятност P да е успешен, то средната продължителност е:
S=N/P (Всъщност малко по-малко, защото когато се изпълни са минали по-малко от N dena) В нашият случай за да е изпълнен е необходимо да се изпълният и 7-те фази. P=p^7, където p е вероятността за изпълнение на всяка фаза и приемаме те да са равни. Та аз получавам минимум при p=0.978 P=0.856, N=4559 - съответно големина на фазите 837, 792, 724, 655, 586, 517, 448. S=5326, то на практика е под 5000, защото когато се изпълни, 7-ия период е около 122 дена, а не 448. Разбира се, след 1 неусешен период фазите на втория могат да се понамалят (на по 500 да речем), но кой знае какво подобрение няма да се получи, защото разчитаме основно на изпълнение от 1-ия път. Така че гооре-долу.....(аз и смятах горе-долу де, така че може да греша)