7. Konáre Metodicky Spraceme vzorové riešenie

Najprv si vysvetlime, čo znamená spojenie „práve vtedy, keď“, pre prípad, že ste ešte nič s týmto spojením nedokazovali. Znamená to, že ak dostaneme nejakú tabuľku, tak buď ju vedia vyprázdniť Mati aj Viktor, alebo ani jeden z nich. Tvrdenie takéhoto typu (tiež nazývané ekvivalencia) sa skladá z dvoch nasledovných tvrdení (implikácií): „Ak tabuľku vie vyprázdniť Mati, tak to vie aj Viktor“ a „Ak tabuľku vie vyprázdniť Viktor, tak to vie aj Mati“. Poriadny dôkaz takéhoto tvrdenia by mal obsahovať dôkazy týchto jednotlivých implikácií. Preto najprv budeme predpokladať, že Mati vie vybrázdniť tabuľku a dokážeme, že ju potom vie vyprázdniť aj Viktor. Bystrý čitateľ už isto tuší, že druhú implikáciu dokážeme vďaka symetrii rovnako.

Matiho ťahy budeme skrátene opisovať ako „Mati si vyberie políčko \(P\)“. Tým myslíme, že Mati vyprázdni stĺpec s políčkom \(P\). Aby mohol takýto ťah spraviť, tak políčko \(P\) musí byť jediné s konárom vo svojom riadku.

Uvažujme teda nejakú tabuľku \(n \times n\) a predpokladajme, že Mati ju vie vyprázdniť. Keďže každým ťahom Mati vyprázdni jeden stĺpec, musí celkovo spraviť \(n\) ťahov. Políčka, ktoré si Mati postupne vyberá, si označíme \(M_1\), \(M_2\), \(\dots\), \(M_n\). Ako môžu byť tieto políčka rozmiestnené v tabuľke? Keďže každý stĺpec Mati vyprázdni práve raz, tak políčka \(M_1, M_2, \dots, M_n\) musia byť v navzájom rôznych stĺpcoch. Taktiež musia byť aj v navzájom rôznych riadkoch: ak by nejaké dve políčka \(M_i\) a \(M_j\) (\(i \ne j\)) boli v rovnakom riadku, tak by Mati nevedel vybrať žiadne z nich – ich spoločný riadok totiž obsahuje aspoň dva konáre.

Ukázali sme tak, že Mati si vyberá políčka \(M_1, M_2, \dots, M_n\) v navzájom rôznych riadkoch aj stĺpcoch. Aby takéto ťahy vedel robiť, tak v tabuľke musí byť celkom dosť kameňov. Skúsme teda o nich zistiť viac. Pri tom, ale aj pri následnom spísaní riešenia, nám vie dosť pomôcť, keď si tabuľku upraceme do pekného tvaru. Vymenenie dvoch riadkov nám neovplyvní to, či Mati alebo Viktor vedia tabuľku vyprázdniť. Rovnako ani výmena stĺpcov nám to neovplyvní. Preto si môžeme riadky aj stĺpce uvažovanej tabuľky preusporiadať tak, že políčka \(M_1, M_2, \dots, M_n\) sa budú v tomto poradí nachádzať na uhlopriečke, teda aby políčko \(M_i\) bolo v \(i\)-tom riadku a \(i\)-tom stĺpci.

Čo teda vieme povedať o zvyšku tabuľky? Prvý riadok okrem políčka \(M_1\) musí byť zaplnený kameňmi, aby mohol Mati vybrať políčko \(M_1\) v prvom ťahu. Napravo od políčka \(M_2\) (v druhom riadku) musia byť tiež samé kamene. Naľavo od \(M_2\), teda prvé políčko druhého riadku, môže byť hocijaký predmet, keďže ho Mati v prvom kole odstráni. Všeobecne povedané, napravo od políčka \(M_k = (k, k)\) musia byť samé kamene, keďže tieto políčka ešte neboli vyprázdnené a v Matiho \(k\)-tom ťahu musí byť políčko \(M_k\) jediné s konárom v \(k\)-tom riadku.

Takto sme ukázali, že napravo od uhlopriečky s políčkami \(M_1, M_2, \dots, M_n\) sú iba kamene. To ale znamená, že Viktor môže políčka vyprázdňovať v opačnom poradí \(M_n, M_{n-1}, \dots, M_2, M_1\). Teda Viktor vo svojom \(k\)-tom ťahu zvolí políčko \(M_{n - k + 1}\). Viktor naozaj môže políčko \(M_{n - k + 1}\) vybrať, keďže nad ním sa nachádzajú iba kamene a všetky políčka pod ním sú prázdne, keďže ich riadky vyprázdnené v predošlých kolách.

Takto sme ukázali, že ak vie tabuľku vyprázdniť Mati, tak ju vie vyprázdniť aj Viktor. V podstate sme dali Viktorovi návod, že vie od Matiho „opisovať“ jeho ťahy, akurát ich musí robiť od konca. Z analogických dôvodov platí, že ak vie tabuľku vyprázdniť Viktor, tak ju vie aj Mati. Presnejšie, tabuľku otočíme o \(90\) stupňov. Tým je naše riešenie dokončené.