10. príklad - Vzorové riešenie

V tomto príklade nemáme až tak uchopiteľné zadanie, ťažko sa nám bude počítať s tabuľkou neznámej veľkosti. Preto je na začiatok asi najlepšie si to vyskúšať pre malé rozmery. Napríklad, pri rozmeroch veľkosti 2 riadky a 3 stĺpce zistíme, že neexistuje ani jeden spôsob, ako splniť zadanie. Podobne si to môžeme všimnúť pre tabuľku 3\times3, alebo vlastne ľubovoľnú tabuľku s tromi, ale napríklad aj piatimi stĺpcami.

Keď si tieto prípady trochu analyzujeme, všimneme si, že keďže v každom riadku musí byť párny počet informácií, tak aj v celej tabuľke bude vždy párny počet informácií. V každom stĺpci je zase nepárny počet informácií, a ak máme v tabuľke nepárne veľa stĺpcov, tak aj celkový počet informácií by musel byť nepárny, čo si protirečí s predošlým tvrdením. Ak je teda v tabuľke nepárny počet stĺpcov, tak sa nedá vyplniť tak, aby bola naraz splnená podmienka pre riadky aj pre stĺpce.

Ďalej potrebujeme zistiť, koľko možností máme v prípade, že je počet stĺpcov párny. V prípade tabuľky 2\times2 sú napríklad iba 2 možnosti – ak si určíme, či v ľavom hornom políčku bude informácia, zvyšok tabuľky sa nám podľa pravidiel určí. Ak by sme ale zvýšili počet riadkov na 3, tak po určení ľavého horného políčka sa nám určí iba prvý riadok. Stále máme možnosť si zvoliť, čo bude v jednom inom políčku, a až vtedy sa nám určí celá tabuľka.

Toto nás môže doviesť k zaujímavému pozorovaniu: Ak v nejakom riadku alebo stĺpci ľubovoľne určíme všetky políčka okrem jedného, tak je jednoznačne určené, či má byť to posledné políčko plné alebo prázdne. Ak ide napríklad o riadok, a vyplnili sme zatiaľ nepárny počet políčok, tak to posledné musíme nutne vyplniť, a vtedy bude riadok vyplnený správne. Rovnako máme práve jednu možnosť aj pre párny počet už vyplnených políčok, a podobne aj pri stĺpcoch.

Zoberme si teda všetky políčka tabuľky okrem posledného riadku a posledného stĺpca, a ľubovoľne ich vyplňme. Teraz nám v každom riadku (okrem posledného) ostáva práve jedno voľné políčko, takže ho vyplníme tak, aby počet informácií v danom riadku sedel. Podobne to urobíme aj pre stĺpce. Takto sme vyplnili celú tabuľku okrem políčka v pravom dolnom rohu, a vieme že sa to dá toľkými spôsobmi, koľkými vieme bez obmedzenia vyplniť tabuľku (a-1)\times(b-1).

Aj políčko v pravom dolnom rohu je jednoznačne určené, máme totiž vyplnený celý zvyšok daného riadku aj daného stĺpca. Tu ale môže nastať problém: čo ak podľa riadku má byť políčko vyplnené ale podľa stĺpca prázdne, alebo naopak? Ak si to vyskúšame pre nejakú konkrétnu tabuľku, zistíme, že sa to nikdy nestáva (stane sa to práve ak je počet stĺpcov nepárny, kde už vieme že je spôsobov 0), skúsme to teda aj dokázať.

Doplňme pravé dolné políčko podľa stĺpca. Dajme tomu, že bol v príslušnom stĺpci nepárny počet vyplnených políčok, a pravé dolné políčko teda necháme prázdne. Keďže sme do nepárneho počtu riadkov dopĺňali informáciu v poslednom stĺpci, tak v časti tabuľky, ktorú sme ľubovoľne vypĺňali, je nepárny počet takých riadkov, ktoré majú vyplnený nepárny počet políčok. Celkovo teda musí byť v tejto časti tabuľky nepárny počet vyplnených políčok.

Teraz sa zaoberáme prípadom, keď je celkový počet stĺpcov párny, a teda v tejto časti tabuľky bez posledného stĺpca bude spolu nepárne veľa stĺpcov. Podobne ako s riadkami, musí byť aj nepárny počet stĺpcov takých, že je v nich nepárne veľa vyplnených políčok aby platilo, že v celej tejto časti tabuľky je spolu nepárny počet vyplnených políčok. Tých zvyšných stĺpcov je teda párne veľa, a práve v nich musíme vyplniť ich posledné políčko. V poslednom riadku celej tabuľky teda vyplníme párny počet políčok, a pravé dolné políčko má ostať aj podľa riadku prázdne.

Ak bol v poslednom stĺpci pôvodne párny počet políčok, musíme pravé dolné políčko vyplniť, a podobne vieme dokázať, že aj posledný riadok bude vyplnený správne.

Ak teda ľubovoľne vyplníme tabuľku bez posledného riadku a stĺpca, máme práve jednu možnosť, ako doplniť zvyšné políčka, aby vyplnenie sedelo. Rozhodovať sa teda môžeme pri (a-1)(b-1) políčkach, pričom pri každom z nich máme nezávisle od seba dve možnosti, ako ho vyplniť. Celkový počet možností je teda 2^{(a-1)(b-1)}.

Pre nepárny počet stĺpcov je teda odpoveď 0, a pre párny počet stĺpcov 2^{(a-1)(b-1)}.