9. úloha vzorové riešenie

Najprv si ošetrime prípad, keď \(m=n=1\), lebo vtedy to jedno políčko nemá suseda, takže obe pravidlá sú splnené bez toho aby nás nejako obmedzovali. Na tom políčku môže byť hocijaké nezáporné celé číslo.

V prípade, že je políčok viac, tak z druhého pravidla vieme, že každé nenulové políčko musí mať za suseda políčko menšie o \(1\) (vďaka prvému pravidlu). Aj ten sused musí mať menšie políčko za suseda (ak nie je nulou), potom jeho sused tiež a tak ďalej, až kým nedôjdeme k nule.

Každá sieť s aspoň dvomi políčkami teda obsahuje nejakú nulu. Môže ich mať aj viac, dokonca môže byť celá vyplnená nulami. Vďaka prvému pravidlu sú susedia núl iba jednotky a nuly. Takže ak máme všetky nuly, tak jednotky sú tiež určené. Susedia jednotiek môžu byť dvojky, jednotky a nuly. Takže ak už v sieti máme všetky nuly a jednotky, tak dvojky sú tiež jednoznačne určené. Podobne, ak máme už určené všetky čísla po \(k\) vrátane, tak všetky \(k+1\) sú nimi určené. Začnime nulami a pozrime sa, či už nám to určí celú tabuľku.

Najprv zistime, kde všade môžu byť nuly. No všade. Musí tam byť aspoň jedna a najviac všetky. To je dohromady \(2^{mn}-1\) možností. Pre každé z \(mn\) polí máme \(2\) možnosti — buď tam nula je alebo nie je. Zo všetkých možností potom musíme odpočítať možnosť, keď nie je žiadna nula.

Keď už máme dané rozloženie núl, tak tabuľka je celá určená. Ďalšie nuly doplniť nemôžeme, tie už sú predsa určené. Na nenulové políčka susediace s nulami dáme jednotky, z prvého pravidla vieme, že iné číslo tam byť nemôže. Iné jednotky tam nebudú, lebo vďaka druhému pravidlu musí mať jednotka za suseda \(0\). Na nevyplnené políčka susediace s jednotkami dáme \(2\). Inde dvojky nebudú, lebo tie musia mať za suseda \(1\). A zase iné čísla na ich mieste byť nemôžu, lebo za suseda majú \(1\). Takto postupne doplníme čísla \(3,\, 4 \dots\), až kým nebude tabuľka plná.

Podľa toho, ako to vypĺňame vidno, že dostaneme záhradu. Každé číslo má susedov s rozdielmi najviac \(1\) a okrem núl má každé menšieho suseda. Treba si však uvedomiť, že je to zároveň jediný spôsob, akým sa dá tabuľka tými číslami vyplniť. Zase to vieme skontrolovať od najmenších čísel. Všetky jednotky sú tam, kde môžu byť a inde byť nemôžu (lebo by nemali za suseda \(0\)) a zároveň na ich mieste nemôže byť iné číslo (lebo by mali za suseda \(0\)). Rovnako s ostatnými, teda \(k\) je na všetkých neobsadených miestach vedľa \(k-1\), nesusedí s menším číslom, lebo tí susedia boli obsadení skôr a na miestach pre \(k\) nemôže pribudnúť iné číslo, lebo najmenší sused bude \(k-1\).

Z núl tak vieme odvodiť celú tabuľku. Zároveň je to jediný spôsob ako tabuľku s tými nulami vyplniť, teda možností je \(2^{mn}-1\) pre sieť s aspoň \(2\) políčkami a nekonečno pre sieť s jedným.