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.

9 komentárov:

Lev bez hrivy povedal(a)...

Rozdel, dobre porataj a panuj!

goober povedal(a)...

A čo keby namiesto dvanástky bola desiatka? Napokon, desať na kvadrát je sto :-)

Radoslav Harman povedal(a)...

goober: úplný súhlas. Desiatka by bola oveľa lepšia. Alebo keď už dvanástka, tak som mal zvoliť 144 vypínačov :)

katka povedal(a)...

Toto je velmi pekne, uz som to videla kedysi davno na nejakom matematickom sustredeni, ale to nebolo so zabou a vypinacmi, ale postupne sa obracali karty (samozrejme ze ich bolo menej ako 100 :)).

Ale ten uvod ma pobavil. Som teraz na jednej konferencii pre PhD studentov (http://www.famnit.upr.si/sl/konference//rogla2013), a asi pred hodinou som sa tu s jednym kolegom rozpravala o futbale :D.

Radoslav Harman povedal(a)...

katka: :) No, ono to je samozrejme len nadsádzka na pobavenie. Aj matematici sa rozprávajú o futbale, dokonca práve na konferenciách mODa sa tradične organizuje futbalový zápas účastníkov. (Obyvkle ho vyhrá to družstvo, za ktoré hrajú naši španielski kolegovia, z ktorých niektorí futbal hrávali aj viac ako len rekreačne.)

Ale inak, čo sa týka tých kariet, tak si ma inšpirovala k novej formulácii tejto úlohy...

katka povedal(a)...

Samozrejme ze to beriam ako nadsadzku :). Mna na tom najviac pobavilo to, ze moj posledny rozhovor predtym, ako som isla pozerat co nove na internete, bol akurat o futbale, a hned na to som si tu precitala taku pre mna aktualnu vetu :).

Aj tu sme mali futbalovy zapas (dokonca aj nejake fotky z toho su: http://tinyurl.com/lyyobrb).

Martin Simo povedal(a)...

http://en.wikipedia.org/wiki/Monolith_(Space_Odyssey)#Appearance_and_capabilities

Po nedavnom citani mi to ostalo v cerstvej pamati a prislo mi ako zaujimava zhoda okolnosti.

Anonymný povedal(a)...

zostanu tie, co maju neparny pocet delitelov - co budu podla vsetkeho druhe mocniny

Radoslav Harman povedal(a)...

Anonymný: Správne, hoci ešte by sa zišlo ukázať, že prirodzené číslo N má nepárny počet deliteľov (medzi číslami 1,...,N) práve vtedy, ak je N druhou mocninou nejakého prirodzeného čísla.