Táto úloha je voľným pokračovaním úlohy 1000 vypínačov.
Ste v miestnosti, v ktorej je vypínač. Neviete čo vypína/zapína a ani sa to nikdy nedozviete. Miestnosť má dvojo dverí – teleportov (napravo a naľavo od vypínača), ktoré vedú do susedných obdobných miestností. Miestnosti sú usporiadané do kruhu a je ich konečný počet, takže keď pôjdete dostatočne dlho dverami vpravo (alebo vľavo), tak sa vrátite do pôvodnej miestnosti. Miestnosti sú rovnaké, nemáte možnosť si nejakú dáko označiť. Môžete akurát vypínač zapnúť, vypnúť alebo ho ignorovať, môžete to urobiť koľkokrát chcete. Každú miestnosť môžete kedykoľvek opustiť ľubovoľnými dverami a kedykoľvek sa do nej vrátiť a vypínač zapnúť/vypnúť/ignorovať. Vypínače sú v náhodnom stave a ovládate ich iba vy.
Vymyslite postup, ktorým dokážete zistiť počet miestností. Najlepšie tak, aby ste sa čo najmenej nachodili.
Riešenie
Označme miestnosť, v ktorej začíname číslom 1 a postupne miestnosti napravo číslami 2, 3, 4, …
- Zapneme vypínač v miestnosti č. 1. Odídeme do miestnosti č. 2.
- Ak je v miestnosti č. 2 vypínač vypnutý, tak pokračujeme 2. bodom.
- Ak je v miestnosti č. 2 vypínač zapnutý, tak ho vypneme a vrátime sa do miestnosti č. 1.
- Ak je vypínač č. 1 vypnutý, tak miestnosti č. 1 a č. 2 sú totožné, t. j. je jediná miestnosť. Koniec.
- Ak je vypínač č. 1 zapnutý, tak pokračujeme 2. bodom.
- Ideme do miestnosti č. 3.
- Ak je v miestnosti č. 3 vypínač vypnutý, tak pokračujeme 3. bodom.
- Ak je v miestnosti č. 3 vypínač zapnutý, tak ho vypneme a vrátime sa do miestnosti č. 1.
- Ak je vypínač č. 1 vypnutý, tak miestnosť č. 1 a č. 3 sú totožné, t. j. sú dve miestnosti. Koniec
- Ak je vypínač č. 1 zapnutý, tak pokračujeme 3. bodom.
- Opakujeme to, čo sme robili doteraz: Ideme do najbližšej miestnosti vpravo, v ktorej sme ešte neboli, a ktorá má zapnutý vypínač. Vypínač vypneme a overíme či sa ne/vypol vypínač v miestnosti č. 1. Pretože je konečný počet miestností, tak skôr či neskôr nastane situácia, že v miestnosti č. x vypneme vypínač a ono to vypne aj vypínač v miestnosti č. 1. Preto miestností bude (x-1).
Problémom tohoto riešenia je, že sa dosť nachodíme. Ak sú všetky vypínače zapnuté, tak:
do č. 2 a naspäť do č. 1: 1+1 prechod dverami
do č. 3 a naspäť do č. 1: 2+2 prechody dverami
do č. 4 a naspäť do č. 1: 3+3 prechody dverami …
To je \(2 (1+2+3+…+n)=2 \frac{n(n+1)}{2}=n(n+1)\), kde \(n\) je počet miestností.
Ak je 1000 miestností, tak je to približne 1 000 000 prechodov dvermi.
Trocha krokov by sme ušetrili, ak by sme pri prvom návrate do miestnosti č. 1 nešli do miestnosti č. 3 ale pre zmenu by sme šli ľavými dverami do miestnosti č. 0. Potom do miestnosti č. 3, potom do miestnosti č. -1, atď. Proste v predchádzajúcom príklade sme reťaz miestností naťahovali doprava – porovnávali sme vypínač v miestnosti č. 1 s vypínačom miestnosti najviac vpravo. Teraz to naťahujeme do dvoch strán, porovnávame č. 1 s č. 2., potom č. 0 s č. 2, potom č. 0 s č. 3, potom č. 3 s č. -1, atď.
V tomto riešení sa nachodíme menej, ale aj tak, ak sú všetky vypínače v najhorších pozíciach, tak:
do č. 2: 1 prechod dverami
do č. 0: 2 prechody dverami
do č. 3: 3 prechody dverami
do č. -1: 4 prechody dverami
do č. 4: 5 prechody dverami …
To je \((1+2+3+…+n)+n=\frac{n(n+1)}{2} +n=\frac{n(n+3)}{2}\), kde \(n\) je počet miestností.
Ak je 1 000 miestností, tak je to približne 500 000 prechodov dverami. To, že tam je \(n (n+3)\) (alebo vyššie \(n (n+1)\)) hovorí, že zložitosť je kvadratická – po roznásobení je najrýchlejšie rastúcim členom \(n^2\).
Oveľa lepší postup vyzerá nasledovne: Prechádzame miestnosti č. 1 až č. \(x\) a zapíname všetky vypínače (pokiaľ je to treba). Otočíme sa, ideme naspäť a zhasíname svetlo vo všetkých \(x\) miestnostiach. Označme celkový počet miestností \(n\), ak \(n\geq x\), tak postupne zapneme (ak sú vypnuté) \(x\) vypínačov a potom ich zhasneme. Ale ak je \(n<x\), tak pri návrate natrafíme na už vypnutý vypínač. Napríklad: \(n=5\) a \(x=8\): Postupne zapneme vypínače \(12345123\). Pri ceste naspäť pôjdeme od konca \(32154321\). Ale keď budeme v miestnosti č. 3 druhýkrát, vypínač tu bude už vypnutý. Podarilo sa nám vypnúť iba 5 vypínačov namiesto 8, preto je jasné, že musí byť 5 miestností!
Idea je, že nemusíme skúšať každé \(x = 1, 2, 3, 4, 5, …\) Stačí postupne skúšať \(x=1, 2, 4, 8, 16, …, 2^k\). Je jasné, že pre každý počet miestností \(n\) existuje jedinečné \(k\) také, že \(2^{k−1}\leq n<2^k\). Počas testu \(2^k\) zistíme počet miestností, \(k =\log_2{n}\) – zaokrúhlené na celé číslo smerom hore.
Počet prechodov dverami (tam a späť) je
\(2(1+ 2+ 4+ 8+ 16+ …+ 2^k)<2\cdot 2^{k+1}= 8\cdot 2^{k-1}\leq 8 n\)
Celkový počet prechodov dverami je iba lineárne závislý od \(n\) a ak je 1 000 miestností, tak bude stačiť menej ako 8 000 prechodov dverami.
Tento postup by sme mohli vylepšiť podobne ako vyššie, chodením striedavo doprava – doľava a počet prechodov by bol polovičný.