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

На шефа на един затвор със 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 години да се оправят