7. Kompletizujeme Múčne Sudoku vzorové riešenie

Pri hľadaní víťazných stratégií v hrách, ktoré sú podobné tejto, sa obvykle hodí nájsť stratégiu pre jedného hráča takú, že má odpoveď na ľubovoľný ťah súpera. Teda to, čo káže stratégia hráčovi urobiť, záleží práve na poslednom ťahu súpera. Keď hráč bude mať odpoveď na ľubovoľný ťah, nemôže sa mu stať, že prehrá (pretože táto odpoveď je ťah, ktorý vie vykonať). Táto stratégia obvykle urobí ťah, ktorý je nejakým spôsobom symetrický voči ťahu súpera, je nejakým jeho odzrkadlením.

Pri tabuľke \(n \times n\) sa ponúka hrať na políčko, ktoré je stredovo súmerné s políčkom, na ktoré hral súper. Toto má tú peknú vlastnosť, že ak je políčko \(A\) zviazané s políčkom \(B\), tak aj políčko \(B\) je zviazané s políčkom \(A\).

Ak je \(n\) nepárne, tak existuje stredné políčko, ktoré je súmerné samé so sebou, pri párnom \(n\) žiadne také políčko neexistuje. Rozlíšime teda prípady podľa parity \(n\).

Párny rozmer tabuľky

Stratégia pre párne \(n\) je pomerne jednoduchá. Hráč zahrá také isté číslo ako hráč pred ním, ale na stredovo súmerné políčko. Bude to teda víťazná stratégia pre druhého (nezačínajúceho) hráča. Potrebujeme však ukázať, že takýto ťah je vždy platný (podľa pravidiel).

Pred ťahom prvého hráča je tabuľka vždy stredovo súmerná, čo sa voľných políčok aj čísel týka. Na začiatku pri prázdnej tabuľke to platí, potom vždy prvý hráč zaplní nejaké políčko, ktorého stredovo súmerné políčko nie je zaplnené (ak by bolo, bolo by aj vybrané políčko už plné). Druhý hráč následne zaplní s ním stredovo súmerné políčko (ktoré je jednoznačne určené) rovnakým číslom a tabuľka je opäť stredovo súmerná.

Toto číslo určite môže byť druhým hráčom umiestnené, pretože ak by sa už v danom riadku alebo stĺpci vyskytovalo, zo symetrie tabuľky sa muselo vyskytovať aj v stredovo súmernom riadku, resp. stĺpci, a teda by bránilo prvému hráčovi zapísať ho.

Pritom druhý hráč nemôže byť zablokovaný práve vykonaným ťahom prvého, pretože pri párnom \(n\) je vždy stredovo súmerný riadok aj stĺpec iný než pôvodný, a teda tento ťah ho nemal ako ovplyvniť.

Nepárny rozmer tabuľky

Nech \(n = 2k-1\) pre prirodzené číslo \(k\). V tomto prípade ukážeme, že vyhrá prvý hráč. V prvom ťahu zahrá číslo \(k\) na prostredné políčko (nemajúce stredovo súmernú dvojicu). V každom ďalšom ťahu odzrkadlí zapísanie čísla \(i\) druhým hráčom tak, že zapíše číslo \(2k - i\) na stredovo súmerné políčko.

Pred ťahom druhého hráča platí, že na každej dvojici stredovo súmerných políčok sú buď čísla so súčtom \(2k = n + 1\), alebo sú obe prázdne (platí to aj pre stredové políčko, pretože \(k+k=2k\)). Pred jeho prvým ťahom to naozaj platí. Potom vždy druhý hráč zapíše číslo \(i\) na nejaké políčko, ktorého stredovo súmerná dvojica je voľná a prvý hráč ju doplní číslom \(2k - i\), čím uvedená vlastnosť platí opäť (podobne ako pri párnom rozmere).

Ak by prvý hráč nemohol umiestniť číslo \(2k-i\), znamenalo by to, že už číslo \(2k-i\) v danom riadku, resp. stĺpci je. To by znamenalo, že v stredovo súmernom riadku, resp. stĺpci už je (na s ním súmernom políčku) číslo \(i\), a teda ani druhý hráč nemohol zahrať \(i\) na zvolené políčko. Jediná možnosť, kedy by táto argumentácia neplatila, je, ak prvého hráča blokuje práve vykonaný ťah druhého hráča. Na to by sa ale museli čísla \(i\) a \(2k-i\) rovnať (aby sa blokovali) a po aplikovaní stredovej súmernosti by muselo ísť stále o ten istý riadok/stĺpec, čiže by muselo ísť o číslo \(i = k\) v prostrednom riadku alebo stĺpci. To sme tam už ale doplnili v špeciálnom prvom ťahu, takže ho nemohol práve zahrať druhý hráč. Prvý hráč tak naozaj môže urobiť svoj súmerný ťah.

Pre párne \(n\) má teda víťaznú stratégiu druhý hráč – Bezzubý a pre nepárne \(n\) prvý hráč – ježibabka.