07 decembra 2008

Prieskumná expedícia (súťažná úloha č.5)

Piatu súťažnú úlohu nám poslal Mišo 'mišof' Forišek, doktorand na FMFI UK.

Na štvorcovej mriežke žije národ panákov. Doteraz obývali polrovinu pod osou x. No teraz kráľ rozhodol, že vyšle zvedov, aby zistili, ako to vyzerá nad osou x.

Na začiatku expedície sa všetci zvedi rozostavia po kráľovstve, teda na navzájom rôzne políčka pod osou x. Následne začne expedícia. Počas expedície sa v každom kroku pohne práve jeden zved. Zvedi sa môžu pohybovať ako kamene v solitéri: Ak má zved v jednom zo 4 hlavných smerov pred sebou iného zveda a za ním voľné políčko, môže ho preskočiť. Preskočený zved už v expedícii nepokračuje.


Príklad povoleného ťahu.


Ľahko zistíme, že na to, aby sme dostali zveda do prvého riadku neznámeho územia, potrebujeme na začiatku zvedov aspoň dvoch, a na dosiahnutie druhého riadku treba zvedov aspoň štyroch:


Optimálne riešenia pre prvý a druhý riadok. V riešení vpravo si všimnite, že v okamihu, kedy najpravejší zved robí skok označený poradovým číslom 2, je už jeho cieľové políčko voľné.


Rozcvička číslo 1. Nájdite optimálne riešenie pre tretí riadok. Prezradíme, že stačí 8 zvedov. (Komu sa fakt nechce, tu nájde jedno možné riešenie. Ale odporúčame pohrať sa, nie je to ťažké.)

Po číslach 2, 4 a 8 je každému jasné, koľko zvedov treba na dosiahnutie štvrtého riadku, že? Až na to, že nemáte pravdu, lebo správny počet je 20.

Rozcvička číslo 2. Nájdite čo najlepšie riešenie pre štvrtý riadok a pochváľte sa v diskusii pod článkom.

No a už sme pri pointe: Použite svoju matematickú intuíciu a tipnite si, koľko najmenej zvedov treba na to, aby sa jeden z nich dostal až do piateho riadku neznámeho územia. A potom skúste nejaké, čo najlepšie riešenie zostrojiť.

Ak sa vzdáte a úlohu nevyriešite, tu je riešenie prezrádzajúce pointu.

(Zdroj: Berlekamp, E. R.; Conway, J. H; and Guy, R. K. "The Solitaire Army.")

2 komentáre:

Peter Richtárik povedal(a)...

Rozcvička 1:

Jedno možné riešenie je položiť piatich panákov k hranici veďla seba v poradí P1, P2, P3, P4, P5 (zľava do prava) a potom troch ďaľších pod panákov P3, P4 a P5.

Týchto 'spodných' troch necháme preskočiť tých nad nimi, a potom P1 preskočí P2.

Sme pri situácii z ktorej sa vieme posunúť o dva riadky hore, takže hotovka.

Peter Richtárik povedal(a)...

Moje riešenie ostatku rozcvičky nájdete na mojom blogu:

"http://predbarakom.wordpress.com
/2008/12/09/
prieskumna-expedicia-riesenie-
rozcvicky/"

[link som zalomil na riadky aby sa nestratil mimo rámčeka].