18 júna 2013

Žaba

Nasledovný hlavolam nám na konferencii mODa10 zadal náš švajčiarsky kolega David Ginsbourger.



Za sebou v rade je 100 vypínačov, ktoré sú na začiatku vo vypnutom stave. Žaba postupne poskáče po všetkých vypínačoch, čím ich zapne. Následne sa žaba vráti na začiatok radu vypínačov a poskáče po každom druhom z nich, čím poskákané vypínače vypne. Potom sa žaba opäť vráti na začiatok a poskáče po každom treťom vypínači, čím zapnuté vypínače vypne a vypnuté vypínače zapne. Potom sa žaba znovu vráti na začiatok radu vypínačov a poskáče po každom štvrtom z nich, čím opäť zapnuté vypínače vypne a vypnuté zapne... Žaba takto preskáče cez rad vypínačov stokrát. Ktoré vypínače budú na konci zapnuté?

Samozrejme, riešenie sa dá veľmi rýchlo nájsť na papieri (alebo pomocou počítača). Pokúste sa však túto úlohu vyriešiť bez akýchkoľvek pomôcok.

 

Nová formulácia úlohy:

Za sebou v rade je nekonečne veľa vypínačov očíslovaných 1,2,3,..., ktoré sú na začiatku vo vypnutom stave. Chuck Norris postupne stlačí každý z nich, čím ich zapne. Následne stlačí vypínače 2,4,6,..., čím všetky stlačené vypínače vypne. Potom Chuck Norris stlačí vypínače 3,6,9,..., čím zapnuté vypínače vypne a vypnuté vypínače zapne. Následne Chuck Norris postláča každý štvrtý vypínač, potom každý piaty a tak ďalej. Ktoré vypínače budú na konci zapnuté?




Ak by ste sa čudovali, ako môže Chuck Norris postláčať toľko vypínačov, tak sa teda nečudujte, lebo je to veľmi jednoduché. Chuck totiž stlačí prvý vypínač za 1/2 sekundy, druhý za 1/4 sekundy, tretí za 1/8 sekundy a tak ďalej. Pri stláčaní každého druhého vypínača vykoná prvé stlačenie za 1/4 sekundy, druhé za 1/8 sekundy, tretie za 1/16 sekundy... Pri stláčaní každého tretieho vypínača vykoná prvé stlačenie za 1/8 sekundy, druhé stlačenie za 1/16 sekundy, tretie za 1/32 sekundy a tak ďalej. Koľko to vlastne bude Chuckovi Norisovi celkovo trvať?

Samozrejme, túto úlohu už vyčerpávajúco nevyriešite len pomocou "podčiarkovania" číselného radu zapísaného na papieri. Teda ... pokiaľ nie ste Chuck Norris.