6. Kráľov Milovaný Štvorček vzorové riešenie

Naše riešenie započnime pohľadom na čiastočne vyplnený štvorec \(2 \times 2\). Ak máme vyplnené tri čísla štvorca, zvyšné číslo je jednoznačne určené. Jednoducho sčítame už existujúce čísla a výsledok musíme odčítať. Tu je tiež dobré uvedomiť si, že ak má byť súčet \(0\), musíme mať rovnako veľa \(1\) ako \(-1\). V každom štvorci sú teda po dva kusy každého čísla a na začiatku sme nemohli mať v jednom štvorci \(2 \times 2\) tri rovnaké.

Predstavme si ďalej, že máme v štvorci \(2 \times 2\) vyplnené len dve čísla. Pre jednoduchosť (a pre ďalší postup) predpokladajme, že máme vyplnený prvý riadok. Ak sú vyplnené čísla rovnaké, máme len jednu možnosť, ako doplniť druhý riadok – musíme dopísať dvakrát to číslo, ktoré v tabuľke zatiaľ chýba. Naopak, ak sú doplnené jedna \(1\) a jedna \(-1\), máme možnosti dve. Dopisujeme tiež jednu \(1\) a jednu \(-1\), takže môžeme dopísať buď rovnaké čísla pod seba, alebo rôzne pod seba. T. j. buď pod \(1\) dopíšeme \(1\) a pod \(-1\) dopíšeme \(-1\), alebo naopak.

Pri dvoch vyplnených číslach teda vždy vieme doplniť daný štvorec \(2 \times 2\) tak, aby spĺňal zadanie. Vidíme teda, že ak budeme mať v štvorci \(2 \times 2\) jedno alebo žiadne číslo, môžeme najprv doplniť štvorec na dve ľubovoľne a stále budeme vedieť pokračovať v dopĺňaní.

Skúsme prejsť na počítanie možných vyplnení tabuľky \(n \times n\). Prvé pozorovanie, ktoré môžeme spraviť na základe predošlého odseku je, že prvý riadok môžeme doplniť ľubovoľne. Po takomto doplnení budú v každom štvorci \(2 \times 2\) najviac dve čísla, a teda sme zatiaľ nič nepokazili. Pre každé z \(n\) políčok sme zvolili jedno z \(2\) čísel. Máme teda \(2^n\) možných doplnení prvého riadku.

Rozlíšime dva typy doplnenia prvého riadku. Buď sa v tomto riadku nachádza dvakrát to isté číslo vedľa seba, alebo nie. Začneme druhým prípadom. Tu máme len dve možné doplnenia. Keďže sa striedajú \(1\) a \(-1\), celý riadok je určený začiatočným číslom. Možnosti sú teda \(1,~-1,~1,~-1,~\ldots\) a \(-1,~1,~-1,~1,~\ldots\). V takomto prípade má každý štvorec \(2 \times 2\) vo vrchnom rade určený prvý riadok a v ňom sú dve čísla. Možnosti na doplnenie zvyšku štvorca \(2 \times 2\) sú teda dve – buď doplníme pod seba rovnaké čísla, alebo rôzne.

Tu je dôležité si uvedomiť, že takáto voľba v jednom štvorci \(2 \times 2\) nám dá jednoznačné doplnenie celého riadku. Akonáhle doplníme jeden štvorec, susedný štvorec (posunutý o \(1\) políčko vpravo/vľavo) bude mať doplnené políčka \(3\), a teda len jednu možnosť. Ešte by sme mali overiť, že táto možnosť bude existovať. Teoreticky by sme sa mohli takýmto doplnením dostať do stavu, keď tieto tri vyplnené čísla sú rovnaké, čo by nevyhovovalo zadaniu. Predpokladali sme však, že vo vrchnom riadku sú dve čísla rôzne, takže táto možnosť nenastane.

Po vyplnení druhého riadku máme opäť riadok striedajúcich sa čísel. Vieme teda opäť rovnako postupovať pri vypĺňaní tretieho, štvrtého, a tak ďalej. V každom z \(n-1\) riadkov (od druhého po \(n\)-tý) sme teda zvolili jednu z dvoch možností. Rovnako sme na tom boli aj v riadku prvom, dostávame tak \(2^n\) vyhovujúcich vyplnení tabuľky.

Prejdime teraz na zvyšné vyplnenia prvého riadku. To je zvyšných \(2^n - 2\) možností. V nich sú vždy niekde dve políčka vedľa seba vyplnené rovnakým číslom. Tieto dve políčka majú pod sebou ďalšie dve, s ktorými tvoria štvorec \(2 \times 2\). Ako sme riešili na začiatku, máme jedinú možnosť ako doplniť tieto dve políčka – doplniť dvakrát opačné číslo, ako je v prvom riadku. Po tomto doplnení dostaneme opäť susedný štvorec (alebo štvorce) \(2 \times 2\), ktoré majú vyplnené tri čísla, a teda máme daný aj zvyšok druhého riadku.

Aj tu nastáva otázka, či sa niečo nemohlo pokaziť. Nemohlo. Do nového riadku sme totiž pod jedno číslo dopísali opačné číslo. A nie len na začiatku. Majme v štvorci \(2 \times 2\) doplnené tri čísla a to štvrté označme \(a\). Vieme, že vedľa \(a\) sú nad sebou napísané dve rôzne čísla, takže susedný stĺpec má súčet \(0\). Aby bol aj celkový súčet štvorca \(2 \times 2\) rovný nule, \(a\) musí dávať s číslom nad sebou tiež súčet \(0\). Ak je nad \(a\) číslo \(-1\), tak \(a = 1\), ak je nad \(a\) číslo \(1\), tak \(a = -1\). Takže sme pod ďalšie číslo dopísali číslo opačné. Ľahko si všimneme, že takto doplnený druhý riadok bude vždy fungovať.

Koľko máme teda možností? Druhý riadok sme mohli dopísať len jedným spôsobom. Tým sme dostali rovnaký riadok ako prvý, len s opačnými znamienkami, takže opäť sú vedľa seba niekde dve rovnaké čísla. Rovnako ako bol jednoznačne určený druhý riadok, bude aj ten tretí, potom štvrtý, a tak ďalej. Pre každé z týchto \(2^n - 2\) vyplnení prvého riadku tak máme len \(1\) možnosť ako vyplniť zvyšok.

Odpoveď: Šachovnicu môžeme podľa zadania vyplniť dokopy \(2^{n+1} - 2\) spôsobmi.