Matematické Fórum

Andrejka3

Ahoj,
tato hra je asi dobře známá (mě až tak ne). Místo termínů hot-spot a cold-spot používám termín modré a magenta místo (viz obrázek)
Problémy:

Autor skryl část textu. Zobrazit/skrýt!

Proč si to nevyhledám na internetu:

Autor skryl část textu. Zobrazit/skrýt!

Problém:
Máme libovolně velkou (čtvercovou) šachovnici, a někde na ní je umístěna dáma. Dva soupeřící hráči se snaží dostat královnu do levého dolního rohu. Ten, kdo ji tam dostane, vyhraje. Dámou lze pohybovat pouze doleva nebo dolů nebo diagonálou doleva dolů.
Ekvivalentní zadání: máme dvě hromádky kamenů. Dva soupeřící hráči se střídají v odebírání kamenů. Ten, kdo odebere poslední kámen, vyhrává. Hráč může v každém tahu provést právě jeden z následujících úkonů: odebrat kladný počet kamenů z jedné z hromádek, či odebrat z každé z hromádek stejný, kladný počet kamenů.
Izomorfismus her: Vyjádříme aktuální pozici královny pomocí souřadnic, jak je na obrázku, tj. číslujeme od nuly. Královna na pozici $m,n$ odpovídá situaci: na jedné hromádce je $m$ kamenů a na druhé $n$ . Korespondence tahů královnou s odebíráním kamenů je zřejmá.
Obrázek:

Některá pozorování a náznak algoritmu vyplnění všech políček:
Hra je symetrická podle diagonály.
Existují místa -- nazvěme je modrá -- kdy hráč na tahu má jistotu výhry (tj. ať soupeř hraje jakkoliv, má vždy možnost správně reagovat a tak zaručit výhru). Zřejmě jsou $m,0$ , $m,m$ , $0,m$ modrými místy, pokud $m>0$ , neboť jsou to všechna místa, ze kterých lze dosáhnout vítězství v jediném tahu. (Doporučené tahy symbolizují šipky procházející modrým místem. Chceme systematicky zjistit všechna tato místa. Existuje určitě algoritmus.) Postupujme podle lexikografického uspořádání $\mathbb{N} \times \mathbb{N}$ . Nalezneme nejmenší neoznačený prvek a označíme jej ``magenta kolečkem''. Toto místo nezaručuje výhru v jednom tahu. Každý tah vede do již označených míst (modrých), tedy každý tah zaručuje prohru. Takovým místům budeme říkat ``magenta''. Jako hráči je naším cílem končit tah vítězstvím nebo magentou. Hra je symetrická. Máme tedy $1,2$ a $2,1$ magenty a víme, že každý tah, který do nich vede je modrý. To jsou právě všechna místa tvaru $a+m,b$ , $a,b+m$ , $a+m,b+m$ , kde $a,b$ je magenta a $m>0$ . Bylo by hezké ukázat, že jsme nalezli všechna místa, ze kterých lze vyhrát za aspoň 2 tahy... (edit: to je část, která je škaredě formulovaná, ale v dalším příspěvku už to mám ok)

Existuje souvislost s Fibonacci posloupností. Dají se podle ní spočítat magenty. Každopádně z obrázku, $1,2$ a $3,5$ a $8,13$ jsou magenty.
Trochu k té hře jsem se vyjádřila ve vláknu kolegy ↑↑ vanok:, děkuji za odkazy.

Andrejka3

↑ Andrejka3:
Pozice, ze které nevede přímá cesta k cíli nebo do magenty, je magenta.
(tedy v každém sloupci (řádku) je nejvýše jedna magenta.)

Algoritmus: Množina označených bodů z $\mathbb{N}\times \mathbb{N}$ označujme $A$ .
$A:=\emptyset$
Krok 0: $A:=A \cup \{(0,m); m>0\} \cup \{(m,m); m>0 \cup \{(m,0); m>0\}\}$ .

Krok 1: $X=\min A'$ je magenta (lexikograf. uspoř.). Každý možný tah vede do již označených míst, modrých.
Je $X=(m,n)$ . $(m,n),(n,m)$ jsou magenty.

Krok 2: K $A$ přidáme tyto dvě magenty a všechna pole, ze kterých se dá do nich dostat. Tj. $(m+k,n)$ , $(m,n+k)$ , $(m+k,n+k)$ , a symetricky pro druhou magentu.
(Do již označených magent se tedy nelze dostat z místa, které není v $A$ )
Pokračuji Krokem 1.

To samozřejmě není konečný algoritmus. Chci ukázat, že běží dost rychle: To je pokud cyklus proběhnul právě $n$ krát, je $[0,n] \times \mathbb{N} \cup \mathbb{N} \times [0,n]$ částí $A$ .
To je ale zřejmé z konstrukce (připomínám, že konstrukce je symetrická v řádcích a sloupcích).

Dokážu, že $\forall m > 0 \exists n>0: \; (m,n) \text{ magenta.}$
V podsstatě jde o to, že se chci v každém sloupci dostat nad šikmé čáry (vedoucí z magent nalevo).
$1,0$ je magenta.
Volme $m>0$ . Po $m$ cyklech máme označené všechny sloupce nalevo od $m$ a i sloupec, kde je $m$ .
$n_0:= \mathrm{max} \{n \in \mathbb{N};\; \exists \tilde{m}<m: \: (\tilde{m},n) \text{ magenta.}\}$
$n_0+m$ je horní odhad, do jaké výšky mohou vést diagonální čáry ve sloupci m.
$(m,n_0+m+1)$ je označená. Je tedy magenta - pak jsme hotovi, nebo modré místo. Pak ale vede přímá cesta do magenty (do cíle nemůže a doleva taky ne). Vede tedy dolů, takže ve sloupci je magenta.

To byla ta lehčí část. Jak uchopit pozorovanou souvislost s Fibonacci posloupností, netuším.

Matematické Fórum

#1 22. 11. 2012 11:10 — Editoval Andrejka3 (27. 11. 2012 16:45)

corner the queen

#2 23. 11. 2012 10:23 — Editoval Andrejka3 (23. 11. 2012 10:50)

Re: corner the queen

Zápatí