piatok 25. mája 2012

Mince na stole

O tom, že ETH je mimoriadne podnetné prostredie svedčí aj kvalita hádaniek, ktoré mi občas odtiaľ posiela môj neraz citovaný priateľ Rišo:

So zakrytými očami vás vovedú do miestnosti, v ktorej sú dva stoly. Na jednom z nich sú rozsypané mince, druhý je prázdny. Dostanete informáciu, koľko mincí je otočených hlavou hore. Mince môžete otáčať a tiež prekladať ich z jedného stola na druhý. Vašou úlohou je zabezpečiť, aby na oboch stoloch bol rovnaký počet mincí, ktoré sú otočené hlavou hore. Ako sa to dá docieliť?

Už len doplním, že je to algoritmická hádanka, mince si môžete predstaviť ako nuly a jednotky. Nie je cieľom hľadať empirické riešenia typu "nahmatám ako vyzerá hlava a ako znak", alebo "hodím všetky mince na zem":-)

4 komentáre:

fedoo povedal(a)...

SPOILER!!:
Zoberiem toľko mincí (je jedno ktoré), koľko ich má byť otočených hlavou hore, prenesiem ich na prázdny stôl a všetky otočím. Škoda, že neviem dokázať, prečo to tak funguje :(

Anonymný povedal(a)...

Zaujimave, ja som sa trapil asi hodinu a nic.

Kazdopadne as mi dza ze fedoo ma pravdu a tu je aj on-th-fly dokaz:

spolu N = (H)ore + (D)ole
Nech zoberiem H minci z kopky H, otocim, dokopy je potom H=0 a sedi.

Nech zoberiem H minci z kopky D, otocim dokopy je potom hore 2H, pricom H+H na jednom resp. druhom stole.

Pokial zoberieme H minci tak ze z kopky H ich zoberieme X a z kopky D ich zoberieme Y (Y+X=H) tak na povodnom stole bude hore mincii H-X a na novom ich bude Y = H-X (qed)

Trocha nestastne som pomenoval aj kopku aj pocet H, ale snad sa to da rozoznat.

A vlastne ta tretia sekcia riesi aj prve dve, ktore su specialny pripad...

rasťo povedal(a)...

Pekne!

Ja som sa s tym inak tiez trapil celkom dost dlhu chvilu. Nakoniec sa mi vyjasnilo znenazdajky a nahle rovno uprostred nedelnej kazne v kostole - moja mysel asi prirodzene zabludila k zrozumitelnejsej teme :-)

fedoo povedal(a)...

Mne to, práveže, netrvalo až tak dlho. Keď som si to prečítal, tak som si myslel, že to bude nad moje sily. Hneď potom som išiel spať a v posteli som na to za chvíľku došiel.

A takým istým spôsobom ako napísal Anonym som si to vlastne overil, takže dokázať som to nakoniec vedel (ak sa to teda môže brať ako dôkaz).