Matematické Fórum

Skrytý text:

Pokusím se svoje řešení vysvětlit metodicky. To znamená, že nebudu rovnou psát ty podstatné myšlenky, ale spíš se pokusím vysvětlit, jak k nim dojít.
Nejprve si asi každý všimne, že hra je v začáteční i koncové pozici (pokud se do ní teda lze dostat) symetrická. Pokud tedy hra půjde dohrát tak, že táhneme v prvním tahu nejlevější zelenou žábou, tak půjde dohrát i tak, že táhneme nejpravější červenou žábou (a naopak). Tato jednoduchá úvaha napadne asi každého. Bohužel sama o sobě na nic není. Nicméně má jeden důsledek: pokud lze vyhrát, určitě lze vyhrát tak, že táhneme nejdřív zelenou žábou. Toto dále budeme bez újmy na obecnosti předpokládat.
Nic tedy prakticky zatím nevíme, nejsme géniové (nebo aspoň já ne) a řešení neumíme uhodnout "z hlavy". Co ale umíme, je zkoušet a hrát si. A přesně to taky budeme dělat. Takže první, co by měl každý při řešení úlohy udělat, je EXPERIMENTOVAT. Tím myslím, že si zkusím hru zahrát pro n=2, n=3. n=4 a sleduji, jak vypadá algoritmus pro výhru v každé z těchto her. Dám sem obrázky, jak vypadá hra pro n=2, n=3, na nichž budu demonstrovat svoji myšlenku:
Pro n=2:


Pro n=3:


Žáby jsem si pro jednoduchost znázornil kolečky (nejsem dobrý malíř) a prázdné místo na kameni je znázorněno pomlčkou. Na každém obrázku je mnoho řádků a tyto řádky jednoznačně zachycují, jak se vyvijí po jednotlivých tazích stav hry. Věřím, že tento krok podrobného rozepsání vývoje (vítězné) hry by zvládl každý, koho by napadlo takto si řešení rozepsat.
Druhá část řešení je založená na pozorování - je potřeba v těchto jednotlivých hrách zachytit nějaké klíčové momenty, kterými hra musí projít a které jsou nějakým způsobem hezky popsatelné. Tak určitě mezi tyto momenty budou patřit začátek a (úspěšný) konec hry, tj. pozice označené značkou (1P) a (4P). To by ale pro popis bylo trochu málo. Všimnu si, že někde před půlkou hry se nezávisle na volbě konkrétního n vyskytuje stav, kdy se střídá zelená a červené žába (začínáme zelenou) a poslední kámen je prázdný. Tento stav označím značkou (2P). Z tohoto stavu se snadno do stavu (3P), kde je situace otočená - začínám prázdným kamenem a pak se střídají žáby červená, zelená, červená, zelená, ... Tento stav je taky docela zajímavý, označím si ho značkou (3P). Pokud si zahrajete hru třeba i pro n=4 nebo n=5 a snažíte se tyto pozice (2P) a (3P) nějak obejít (a přitom neprohrát), sami uvidíte, že se jim nevyhnete. Toto ale samo o sobě není důkaz. Klíčová myšlenka je ale ta, že si toho všimneme (tvoříme hypotézu).
Pro nás by však bylo výhodné ukázat, že se nezávisle na volbě n mohu vždy ze stavu (1P) dostat do stavu (2P), ze stavu (2P) do stavu (3P) a konečně ze stavu (3P) do stavu (4P). Podúloha (2P) -> (3P) je vcelku jednoduchá a je vidět, jak ji provedeme obecně, tudíž to zde nebudu rozepsisovat. Dále si všimnu, že podúloha (1P) -> (2P) úzce souvisí s podúlohou (3P) -> (4P) - svým způsobem se jedná vlastně o to samé (zaměňte pojmy "levo" a "pravo"; "hrát" a "hrát pozpátku" a uvidíte, že se jedná o stejné podúlohy). Takže vyřešíme-li podúlohu (1P) -> (2P), máme vyřešenou i podúlohu (3P) -> (4P). Takže celá úloha se redukuje na řešení podúlohy (1P) -> (2P).
Snažíme se tedy vyřešit tuto podúlohu:

Zde přichází důležitá myšlenka, kterou jsem poradil už v hintech, a to použít indukci. Je však potřeba rozmyslet si, co bude indukční předpoklad. V mém případě bude trochu rozsáhlejší a to proto, že si to řešení úlohy vyžádá (jak sami uvidíte). Náš indukční předpoklad bude, že dokážeme vyřešit všechny podúlohy (1P) -> (2P), (2P) -> (3P), (3P) -> (4P) pro dané n.
Kromě toho ale taky zřejmě umíme vyřešit i podúlohy (1U) -> (2U), (2U) -> (3U), (3U) -> (4U). Proč? Protože třeba řešení (1U) -> (2U) vznikne z řešení (1P) -> (2P) tak, že budeme hrát všechny tahy symetricky k tomuto původnímu.
Jak se tedy dostaneme pro n+1 žab na každé straně ze stavu (1P) do stavu (2P) ?
Takto:

Tím je se tedy umíme obecně dostat ze stavu (1P) do (2P). Analogicky by se dokázalo, že se umíme dostat z (1U) do (2U). Z předchozích úvah se tedy umíme dostat i pro n+1 do stavů (3P), (4P), (3U), (4U). Tím je indukce ukončena a důkaz tím pádem taky. Současně se jedná i o návod, jak řešení zkonstruovat (rekurzivně). Počet tahů pro dohrání lze už ze zmíněných úvah snadno odvodit.