Matematická hádanka – určete kolika vězňům se podaří uprchnout z cely

Po delší době se díky čtenáři s přezdívkou NoNomino vracím k matematické hádance. Správné řešení sám zatím neznám, a jednoduchou úvahou jsem na něj nepřišel. Asi zkusím do řešení zapojit počítač ;-).

Zadání hádanky zní následovně:

Je dána kruhová věznice s jednolůžkovými celami s dveřmi očíslovanými 1 až 100, s plnou kapacitou a s žalářníkem. Jednou se žalářník opije a pod vlivem alkoholu začne systematicky obíhat věznici s tím, že každé dveře, u kterých se zastaví, pokud jsou zamčené odemkne, jinak je zamkne. Počítat začíná pokaždé u těch samých (pro jednoduchost u prvních). Celkem oběhne věznici 100krát a to tak, že

při každém i-tém oběhu odemkne každé i-té dveře (tj. při i-tém oběhu n-té dveře odemkne pokud n mod i=0 neboli při prvním odemkne každé, při druhém každé druhé, při třetím každé třetí, .. , při stém každé sté).

Otázka zní: kolika vězňům se podaří uprchnout z cely? (pro upřesnění bych ještě dodal, že vězní během obíhání žalářníka spí tvrdým spánkem a probudí se až někdy přibližně po posledním oběhu a před první kontrolou věznice, dále, že každý z nich touží po svobodě, jsou pohybu schopní, v cestě z cely jim bránily nebo brání jen dveře této cely, dveře jsou zevnitř neodemknutelné a každý vězeň ostatní vězně a cizí dveře ignoruje).

Nápověda: řešení by mělo být univerzální pro libovolný počet cel, pokud by to někdo chtěl počítat oběh po oběhu, umocněte počet cel nějakým pěkným číslem:-), úlohu by možná někdo chtěl řešit programem, v tom případě je řešením nejefektnější algoritmus (a to pracující v konstantním čase:-) ).

Tolik k hádance vše. I když v hádance není uveden počáteční stav, předpokládám, že jsou na počátku, před prvním oběhem opilého žalářníka všechny cely zamčené. Pokud ne, prosím zadavatele o opravu.

Na závěr přidám slíbenou správnou odpověď k hádance Nedělní foto hádanka – poznáte restauraci dle zadaných indicií . Dle autorky se jedná o Belvedér.

You can skip to the end and leave a response. Pinging is currently not allowed.

3 komentáře k “Matematická hádanka – určete kolika vězňům se podaří uprchnout z cely”

  1. matej21 napsal:

    pokud sem dobre pochopil zadani a dobre napsal script tak jich zustane otevrenych 10, nepletu se?

  2. matej21 napsal:

    takze pokud jsem zadani dobre pochopil tak je zde univerzalni vysledek pro libovolny pocet cel: odmocnina z poctu cel zaokrouhlena dolu

  3. Štěpán F. napsal:

    To matej21:
    Neznám sice správné řešení, ale zkusil jsem si modelovat úlohu pro 1-10 cel a pro tyto počty cel mi tvoje obecné řešení vyhovuje, takže by to asi mohlo být správně.

    Doufám, že se zde objeví i algoritmus na správný výpočet.

Napište prosím komentář

You must be logged in to post a comment.