10. Kúzelná Minihra Starčeka vzorové riešenie

Keďže nás zaujíma iba parita čísel v tabuľke, môžeme sa na ňu pozerať modulo \(2\). Ťah v takejto tabuľke znamená zmenu parity každého čísla vo vybranom riadku a stĺpci. „Ťahaním“ políčka \((i, j)\) označme zmenu parity políčok v riadku \(i\) a stĺpci \(j\). Riešenie rozdelíme na dva prípady, a to na párne \(n\) a na nepárne \(n\).

Párne \(n\)

Pri tabuľke párnych rozmerov vieme opísať postup, ako zmeniť paritu iba jedného zvoleného políčka. Ak chceme zmeniť paritu políčka v \(i\)-tom riadku a \(j\)-tom stĺpci, vieme to spraviť v \(2n-1\) ťahoch tak, že postupne budeme ťahať políčka z riadku \(i\) a stĺpca \(j\) tak, aby sme na každom vykonali práve jeden ťah.

Môžeme si premyslieť, že takýmto spôsobom zmeníme paritu políčka \((i, j)\) presne \(2n-1\) krát (keďže meníme jeho paritu každý ťah). Pre ostatné políčka v riadku \(i\) a stĺpci \(j\) platí, že ich paritu zmeníme práve \(n\) krát. Tým pádom sa ich parita nezmení. Všetky ostatné políčka zmeníme práve dvakrát, čiže sa im tiež parita nezmení. Jediným políčkom so zmenenou paritou teda bude \((i, j)\).

Opakovaním tohto postupu pre všetky nepárne políčka v tabuľke dospejeme k tomu, že v tabuľke budú iba párne čísla. Tiež si vieme ľahko premyslieť, že tento postup ide aplikovať bez ohľadu na začiatočné čísla v tabuľke. Pre tabuľku \(n\times n\) párnych rozmerov teda vieme mať presne \(n^2\) párnych čísel.

Nepárne \(n\)

Ako dolný odhad pre nepárne \(n\) môžeme použiť výsledok z predchádzajúceho prípadu. Ak si zoberieme tabuľku \((n-1)\times (n-1)\) (odobratím spodného a pravého riadku), vieme v nej zmeniť všetky čísla na párne. Tým pádom vieme dostať minimálne \((n-1)^2\) párnych čísel.

Ostáva už len zistiť, čo dokážeme spraviť s číslami v pravom stĺpci a spodnom riadku. Ťahaním pravého dolného políčka sa žiadne z čísel v tabuľke \((n-1)\times (n-1)\) nezmení. Takýmto ťahom však dokážeme zmeniť paritu všetkých ostatných čísel. Týchto čísel je \(2n-1\). Ak by bolo \(n\) alebo viac z nich nepárnych, vedeli by sme spraviť ťah na pravé dolné políčko a zmeniť ich na párne. Ak by nepárnych bolo menej ako \(n\), znamenalo by to že máme aspoň \(n\) párnych čísel. Na základe toho vieme povedať, že dokážeme v poslednom riadku a poslednom stĺpci mať aspoň \(n\) párnych čísel. V celej tabuľke teda vieme dostať aspoň \((n-1)^2+n = n^2-n+1\) párnych čísel.

Poďme teraz dokázať, že existujú také konfigurácie tabuľky, pre ktoré viac ako \(n^2-n+1\) párnych čísel dostať nevieme. Nazvime si párne/nepárne riadky a stĺpce také, ktorých súčet čísel je párny/nepárny. Kľúčovým invariantom v tomto prípade je, že každý jeden ťah zmení paritu všetkých stĺpcov aj riadkov. Ak teda začíname s tabuľkou, v ktorej je \(k\) nepárnych stĺpcov a \(l\) nepárnych riadkov, vieme sa pohybovať iba medzi dvoma stavmi – buď máme \(k\) nepárnych stĺpcov a \(l\) nepárnych riadkov, alebo \(n-k\) nepárnych stĺpcov a \(n-l\) nepárnych riadkov.

Pozrime sa na tabuľku, v ktorej sú čísla v políčkach \((n, 1), (n, 2), \dots, (n, n-1)\) posledného riadku nepárne a všetky ostatné sú párne. Takáto tabuľka má \(n-1\) nepárnych stĺpcov a \(0\) nepárnych riadkov. Tiež vieme, že ak vykonáme párny počet ťahov, situácia s riadkami a stĺpcami sa nezmení, a ak vykonáme nepárny počet ťahov, budeme mať \(1\) nepárny stĺpec a \(n\) nepárnych riadkov. V oboch prípadoch máme aspoň \(n-1\) nepárnych stĺpcov/riadkov. Nepárny stĺpec/riadok znamená, že obsahuje aspoň jedno nepárne číslo, z čoho vieme usúdiť, že budeme vždy mať aspoň \(n-1\) nepárnych čísel v tabuľke. Teda pre takúto tabuľku je \(n^2-n+1\) párnych čísel maximum.

Pre nepárne rozmery tabuľky teda vo všeobecnosti vieme dosiahnuť maximálne \(n^2-n+1\) párnych čísel.

Záver

Pre tabuľku \(n\times n\) sme v závislosti od parity \(n\) našli hodnoty \(N\): \[N = \begin{cases} n^2 & n = 2k\\ n^2-n+1 & n = 2k-1 \end{cases} \qquad k\in\mathbb{N}\]