Zadanie
Milý denníček,
dnes som sa zobudil s chuťou na bravčovinu, i keď po týždni bez jedla by som zjedol aj sirôtky zo záhrady. Vydal som sa teda do Prasačiniec, aby som si pochutil. Hneď skraja dediny som videl slamený domček. Tak som doň fúkol, až po ňom nič neostalo. Ale domáceho nikde. Hneď vedľa stál druhý domček, tentoraz drevený. Tak som doň fúkol, až po ňom nič neostalo, ale domáceho opäť nikde.
Tretí dom bol z kameňa a popísaný číslami. Spredu vyzeral ako tabuľka \(n \times n\), pričom \(n \geq 3\). V každom políčku je vpísané číslo \(1\) alebo \(2\), pričom v každom obdĺžniku \(2 \times 3\) alebo \(3 \times 2\) je párny súčet. Vzhľadom na \(n\) určte, koľkými spôsobmi mohla byť takáto tabuľka vyplnená.
Nech som fúkal, ako som fúkal, tento dom som nerozfúkal.
Vyberme si nejaké vyplnenie prvých troch políčok prvého riadku a prvých dvoch políčok druhého riadku. Ukážeme, že teraz už vieme celý zvyšok tabuľky vyplniť práve jedným spôsobom.
Zaveďme si značenie, kde políčko \((x, y)\) bude v \(x\)-tom stĺpci a \(y\)-tom riadku. Políčko \((3, 2)\) vieme určiť jednoznačne z obdĺžnika od \((1, 1)\) po \((3, 2)\), čím ho celý vyplníme.
Z tohto obdĺžnika vieme ďalej jednoznačne určiť aj políčko \((1, 3)\): obdĺžnik od \((1, 2)\) do \((3, 3)\) nám určuje paritu riadku od \((1, 3)\) po \((3, 3)\) a obdĺžnik od \((2, 1)\) po \((3, 3)\) určuje paritu iba dvoch pravých políčok \((2, 3)\) a \((3, 3)\), z čoho už jednoznačne dostávame \((1, 3)\). Potom vieme zrejme doplniť aj políčko \((2, 3)\) a potom aj \((3, 3)\).
Takto si teda vieme zobrať vyplnený \(2\times 3\) obdĺžnik a jednoznačne ho rozšíriť na \(3\times 3\). Potom si môžeme zobrať ten dolný \(2\times 3\) obdĺžnik z nášho novovyplneného štvorca \(3\times 3\) a ten ďalej rozšíriť, a tak ďalej, čím vyplníme celé prvé tri stĺpce. Symetricky vieme takto vyplniť prvé tri riadky. No a potom už zrejme vieme vyplniť celú tabuľku.
Takto sme dokázali, že ak nejaké vyplnenie pre daných prvých \(5\) políčok existuje, tak je jednoznačné, ale musíme overiť, či také vyplnenie aj naozaj existuje (mohlo by sa stať, že takto získané vyplnenie v skutočnosti nie je platné).
Zostrojíme vyplnenie tabuľky pre prípady, keď je medzi prvými piatimi políčkami iba jedna jednotka a všetky ostatné sú dvojky. Vždy vyplníme ľavý horný \(3\times 3\) štvorec a ním vydláždime zvyšok tabuľky, stačí teda overiť, že vyhovujú súčty v obdĺžnikoch v tomto štvorci, vrátane tých „cez okraj“ (teda tretí a prvý riadok/stĺpec). Pre prehľadnosť namiesto dvojok budeme písať iba bodky.
\[\begin{align} &\begin{matrix} 1 & \cdot & \cdot \\ \cdot & \cdot & 1 \\ \cdot & 1 & \cdot \end{matrix} & &\begin{matrix} \cdot & 1 & \cdot \\ \cdot & \cdot & 1 \\ 1 & \cdot & \cdot \end{matrix} & &\begin{matrix} \cdot & \cdot & 1 \\ \cdot & \cdot & 1 \\ 1 & 1 & 1 \end{matrix} & &\begin{matrix} \cdot & \cdot & \cdot \\ 1 & \cdot & 1 \\ 1 & \cdot & 1 \end{matrix} &\begin{matrix} \cdot & \cdot & \cdot \\ \cdot & 1 & 1 \\ \cdot & 1 & 1 \end{matrix}\end{align}\]
Tabuľka so samými dvojkami tiež funguje. Ak chceme mať medzi prvými piatimi políčkami viac jednotiek, môžeme zobrať súčet (po prvkoch modulo \(2\)) tých tabuliek, ktoré majú jednotky na príslušných miestach a dvojky na tých ostatných. Ak totiž nejaké dve tabuľky spĺňajú podmienku v zadaní, potom ju spĺňa aj takýto ich súčet.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.