» Main » Messages  000000010011000011 

Vězni budou postupovat obdobně jako jsem popsal v úloze 100 vězňů a 1 žárovka. Je tedy jeden sčítač, který eviduje, kolik vězňů již místnosti bylo. Když mají k dispozici 2 žárovky, můžou je navíc využít jako jednoduché počítadlo. Postupovat budou následovně:
Sčítač uvede světla vždy do výchozího stavu např. obě žárovky vypnuté - stav 0 = (0,0). Pokud vejde do místnosti jiný vězeň, zvýší stav o 1 výše (stav 1 = (0,1), stav 2 = (1,0), stav 3 = (1,1)). Toto udělá pouze jedenkrát (aby ho mohl sčítač započítat) a při dalších návštěvách místnosti už nedělá nikdy nic. Nic neudělá vězeň ani v případě, kdy sice je v místnosti poprve, ale žárovky jsou již ve stavu 3. Pokaždé, když se do místnosti znovu dostane sčítač, může si započítat tolik vězňů, jaký je stav světel (0 až 3). Když má napočítáno 99 vězňů. Může prohlásit, že tam již byli všichni.
A jaký je nejmenší počet dnů - nejkratší scénář? První tři dny jdou do místnosti 3 různí NEsčítači. První z nich ví že je první a ať je výchozí stav jakýkoliv, uvede místnost do stavu 1. Další pak postupují již podle výše napsaného. Sčítač pak přijde do místnosti každý 4 den, aby si započítal 3 vězně. Ti se v ostatních dnech musí všichni vystřídat. Je jich bez sčítače 99, zvládnou to tedy na 99/3 = 33 cyklů po 4 dnech = 132 dnů.
Otázka druhá je, s jakou pravděpodobností může nastat právě tento scénář, nicméně je to ten nejkratší možný.

Jsem úplně zblblý, zhasínal by jenom ten, který byl už alespoň jednou v jiné, než plně rozsvícené místnosti. Pokud tedy sčítač najde poprvé plně rozsvícenou místnost, jedno světlo by zhasnul a až při další návštěvě by zase rozsvítil. Pokud by mu ovšem zhasnul někdo jiný, započetl by ho. Sám by to takhle neustále střídal, aby měl jistotu že každý vězeň má šanci být v jiné než plně rozsvícené místnosti a zároveň měl možnost dát to najevo. Snad už nevynechal žádnou možnost, přo které by se to mohlo pokazit (mimo, s touhle úpravou není potřeba zdvojnásobovat protokol, stačí jej provést jednou)

Shrnuto podtrženo, vězeň, který už byl v místnosti, kde nesvítila obě světla a teď v ní, jedno světlo zhasne a dává si relax. V každém jiném případě vězeň pouze čeká na svoji příležitost být započtený. Sčítač, aby zařídil každému možnost být v místnosti, kde nesvítí obě světla, pokud sám dojde do takové místnosti, jedno světlo zhasne. Potom při další návštěvě světlo zpátky rozsvítí. Pokud dojde do místnosti, kde svítí jedno světlo a sám jej nezhasnul, připočte si na svém počitadle 1. Jakmile bude mít 99, hra končí.

Tak, teď by neměl být v ničem zádrhel.

Pokud opomenu stárnutí a budu uvažovat, že tohle budou provádět do nekonečna, jde to pomocí sčítače, kterého na začátku vyberou.

Sčítač bude vždy rozsvěcovat na max, každý kdo dojde do plně rozsvícené místnosti, jedno světlo zhasne a od této chvíle už nebude na nic sahat. Ve všech jiných stavech (jedno světlo svítí nebo je zcela zhasnuto vězni nebudou dělat vůbec nic). Jakmile sčítač (po té, co alespoň jednou rozsvítil všechna světla) narazí na jedno rozsvícené světlo, znovu rozsvítí a započte si jednoho vězně. "Komunikační protokol" si potom zopakuje s dalším vězněm, kdy na konci jej opět započte (protože tento vězeň opět už nebude na nic sahat). Jakmile tento protokol sčítač zopakuje 99x, má jistotu, že se všichni vězni vystřídali.


Ale jak říkám, tohle by fungovalo, kdyby měli miliony let času :)

Vlastně by to musel každý udělat 2x, a až potom přestat cokoli dělat, jinak by jim mohl jeden chybět, ale pokud každý zhasne 2x v plně rozsvícené místnosti, budou mít jistotu, že jedno z těch zhasnutí následovalo po té, co tam rozsvítil sčítač. Ten by tím pádem musel napočítat celkem 198 protokolů. Omlouvám se za nedostatek.

Pokud opomenu stárnutí a budu uvažovat, že tohle budou provádět do nekonečna, jde to pomocí sčítače, kterého na začátku vyberou.

Sčítač bude vždy rozsvěcovat na max, každý kdo dojde do plně rozsvícené místnosti, jedno světlo zhasne a od této chvíle už nebude na nic sahat. Ve všech jiných stavech (jedno světlo svítí nebo je zcela zhasnuto vězni nebudou dělat vůbec nic). Jakmile sčítač (po té, co alespoň jednou rozsvítil všechna světla) narazí na jedno rozsvícené světlo, znovu rozsvítí a započte si jednoho vězně. "Komunikační protokol" si potom zopakuje s dalším vězněm, kdy na konci jej opět započte (protože tento vězeň opět už nebude na nic sahat). Jakmile tento protokol sčítač zopakuje 99x, má jistotu, že se všichni vězni vystřídali.


Ale jak říkám, tohle by fungovalo, kdyby měli miliony let času :)

Budou-li se vězni znát, poslední počká než všechny ostatní vězně popraví a on řekne, že se všichni přeživší v místnosti vystřídali.

Skutečně můžou manipulovat jen s přepínáním žárovek. Není povoleno nic vyrývat na zeď nebo cokoliv měnit apod.

Ahoj nemam reseni, jen otazku, myslim, ze zadani neni napsany jednoznacne. Muzou tam vezni s necim jinym manipulovat nez jen rozsvicet a zhasinat=muzou tam po sobe neco nechat, vyryt neco apod? ja si myslim, ze asi ne (pak me teda zatim nenapada, jak to vyresit). Prosim te, jestli skutecne nemohou, dopis to do zadani, nebo mi odpovez na mail proespo2zavinacseznam.cz.Diky moc K.

99