Zadanie

V New Yorku sú obľúbené štvorčekové siete. Preto aj kvetinový záhon v Central Parku má tvar štvorčekovej siete \(m\times n\) políčok. V každom políčku rastie jeden typ kvetiny -- nezáporné celé číslo. Takýto záhon sa nazýva záhradou, ak sú splnené nasledujúce dve podmienky:

  • Rozdiel čísel na dvoch políčkach, ktoré susedia stranou, je 0 alebo 1.
  • Ak je číslo v nejakom políčku menšie alebo rovné ako číslo na všetkých políčkach susediacich stranou, tak je rovné 0.
V závislosti od kladných celých čísel \(m\) a \(n\) určte, koľkými spôsobmi môžu byť v záhone vysadené kvety, aby tvoril záhradu.

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.

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ť.

  • Radek Olšák

    25. marec 2017 21:29

    Formálně vzato je v případě m=n=1 jen jedna možnost jak záhon osázet. Pro jediné políčko tohoto záhonu se totiž ptáme na univerzální kvantifikaci přes prázdnou množinu, která se zavádí jako "true". Takže v tomto políčku musí být 0.