V miestnosti je sto krabičiek uložených v jednom rade. V každej je meno jedného zo sto väzňov (žiadni dvaja sa nevolajú rovnako) a meno každého väzňa je práve v jednej krabičke. Každý väzeň je vpustený dnu a môže sa pozerať do krabičiek, otvoriť ich môže však najviac 50. Po jeho odchode musí miestnosť ostať presne v takom istom stave, ako keď do nej vošiel. Ak sa každému väzňovi podarí nájsť jeho meno, tak sú všetci voľní. Väzni sa môžu na začiatku poradiť, ale potom ich odvedú na samotky a do miestnosti vodia postupne. Ako sa majú dohodnúť, aby maximalizovali šancu na úspech?Ondrejov komentár: "Ak by sa väzni správali náhodne a navzájom nezávisle, je zrejmé, že šanca na priepustku je polovica umocnená na 100. Dá sa však vymyslieť postup, pri ktorom dostanú väzni priepustku s cca 30% šancou. Riešenie tejto úlohy sa dá celkom ľahko pochopiť, je veľmi elegantné a nápadité. O to ťažšie je na to dôjsť sám. Ja som to nevydržal a po polhodine uvažovania som si pozrel vzorové riešenie. Ale aj dosť veľké hlavy (kamaráti Česi na súťaži v Bulharsku a mnohí ďalší) si nad tým lámali hlavy a bezvýsledne..."
Úloha je prevzatá. Vzorové riešenie je uvedené na tejto stránke (pdf).
Hehe, na tento príklad si spomínam veľmi dobre. Prvýkrát som ho riešil na súťaži v programovaní: http://acm.uva.es/contest/data/0156/problemset/a.html
OdpovedaťOdstrániťAko vidieť z výsledkovky http://acm.uva.es/contest/rankfinal.php?c=0156, zadanie A nevyriešil za 5 hodín skoro nikto. A riešitelia nie sú žiadne B-čka. V prvej 20-ke sú samé známe mená :-)
Naozaj krásna úloha!
OdpovedaťOdstrániťNejaký čas som sa zamýšlal, ale keď som videl, že moje úvahy nikam nevedú, tak som si riešenie prečítal.
Mám pocit, že na toto by som teda neprišiel ani za niekoľko dní. A možno vôbec. Analýzu beriem, to sa dá (i keď by sa mala dať zlepšiť kvoli tomu, že tie javy nie sú nezávislé) keď už viete čo analyzovať.
Ešte raz: nádherná úloha, veľmi sa mi páči!
Je to pěkná úloha, ale je třeba si uvědomit jednu věc. Postup uvedený ve vzorovém řešení nebude fungovat pokud by vězeň neměl 50, ale např. jen 25 pokusů. Lépe se to vysvětlí na tom příkladu (v PDF), kde je uvažováno 8 krabiček a 4 pokusy. Pokud povolíme jen 2 pokusy, pak součet 1/3 + 1/4 + 1/5+ 1/6 + 1/7 + 1/8 bude už větší než 1, což je pro pravděpodobnost hodnota nemožná. Vtip je v tom, že pro menší počet pokusů se mohou vyskytnout některé delší cykly (jejichž pravděpodobnosti se odečítají) současně, např. 3 a 5 vedle sebe, kdežto v původním zadání se dva cykly délky 5 vedle sebe nevešly, takže pravděpodobnosti byly nezávislé.
OdpovedaťOdstrániťZkuste úlohu zobecnit na n pokusů a k krabiček, výsledek může být docela zajímavý. Úloha má jistě řešení i pro k < n/2, ale pravděpodobnost se musí počítat trochu jinak.
A ještě poznámku, výpočet těch dílčích pravděpodobností (cyklů) jsem řešil (ve zcela jiné souvislosti) už v roce 2003 v tomto článku
http://web.telecom.cz/vaclav.kotesovec/pocetcykl.htm
(Jaký je počet možných cyklických záměn ? - myšleno v šachových úlohách). Takže mohu potvrdit, že řešení je správné.
V odstavci výše jsem chtěl napsat
OdpovedaťOdstrániťk pokusů a n krabiček
(v originálním příkladu je k=n/2)
Zistil som ešte ďalšie fakty k tejto úlohe:
OdpovedaťOdstrániť1. Túto úlohu prvý raz formulovali (v nejakom článku) Peter Bro Miltersen a Anna Gál. Riešenie ako prvý objavil Sven Skyum.
2. Curtin a Warshauer dokázali, že lepšia stratégia neexistuje. Ak viete, ako sa dá dosiahnuť tých 30 percent, tak to vôbec nie je ťažké. Stačí len trochu upraviť hru, tak aby mali väzni viac šancí.