Táto úloha je voľným pokračovaním úloh Tri vypínače a Veľa vypínačov.
Ste v miestnosti, v ktorej je 1000 vypínačov. V inej miestnosti, do ktorej nevidíte, je 1000 žiaroviek, každá z nich je ovládaná práve jedným vypínačom z prvej miestnosti. Vypínače sú v náhodnom stave a ovládate ich iba vy. Môžete každý vypínač zapnúť, vypnúť alebo ho ignorovať, môžete to urobiť koľkokrát chcete. Z miestnosti s vypínačmi môžete kedykoľvek odísť do miestnosti so žiarovkami. Po kontrole, ktoré žiarovky svietia sa môžete vrátiť a vypínače znova zapnúť/vypnúť/ignorovať. A potom zasa môžete ísť do miestnosti so žiarovkami …
Vymyslite postup, ktorým dokážete každému vypínaču priradiť jeho žiarovku. Najlepšie tak, aby ste sa čo najmenej nachodili (medzi miestnosťami).
Okrem vypnutia a zapnutia vypínača, kontroly či žiarovka svieti si môžete každý vypínač a každú žiarovku ľubovoľne označovať.
Riešenie
Najjednoduchší postup je vypnúť všetky vypínače okrem jedného a ísť sa pozrieť, ktorá žiarovka svieti. To by znamenalo 999 kontrol (posledný vypínač a poslednú žiarovku netreba kontrolovať). Dá sa to ale urobiť výrazne úspornejšie.
Polovicu vypínačov označíme “0” a vypneme ich. Druhú polovicu označíme “1” a zapneme ich. Odídeme do miestnosti so žiarovkami a svietiace označíme “1” a ostatné “0”. Vrátime sa k vypínačom.
Máme dve skupiny (“0” a “1”). Každú rozdelíme na polovicu, vypneme/zapneme vypínač a dopíšeme napravo do označenia “0” alebo “1”. Dostaneme 4 skupiny: “00”, “01”, “10”, “11”. Odídeme k žiarovkám a dopíšeme k označeniu ak svietia “1”, inak “0”. Vrátime sa k vypínačom.
Opakujeme predchádzajúcu činnosť. Ak nejaká skupina sa nedá rozdeliť na presnú polovicu, tak ju rozdelíme približne, napríklad 125 rozdelíme na 62 a 63.
1000 môžeme deliť na “polovice” maximálne 10krát, pretože \(2^{10}=1024\).
Preto na desiatu návštevu miestnosti so žiarovkami vieme presne, ktorý vypínač ovláda ktorú žiarovku.