10. príklad - Vzorové riešenie
Zadanie
Majme tabuľku n\times n. Cesta nech je ľubovoľná postupnosť susedných políčok, ktorá vedie z ľavého horného do pravého dolného rohu tak, že ideme len doprava a dole. Koľkými spôsobmi vieme políčka tabuľky ofarbiť na biele a čierne tak, že všetky cesty obsahujú rovnaký počet čiernych políčok?
Vzorové riešenie
Prvé políčko cesty je v ľavom hornom rohu tabuľky. Druhé môže byť od neho doprava alebo dole. Tretie políčko musí byť doprava alebo dole od nejakého druhého, a tak ďalej. Keď si ku každému políčku napíšeme, v ktorom kroku ho môžeme navštíviť, bude to teda vyzerať nejak takto:
\displaystyle\begin{matrix} 1 & 2 & 3 & 4 & \cdots \\ 2 & 3 & 4 & 5 \\3 & 4 & 5 \\ 4 & 5 & & \ddots \\ \vdots & & & & \end{matrix}
V každom kroku sa musíme pohnúť na ďalšiu uhlopriečku. Ak by sme teda každú uhlopriečku ofarbili celú na rovnakú farbu, také ofarbenie určite bude vyhovovať zadaniu. Nedala by sa však tabuľka ofarbiť aj nejako inak? Pozrime sa na to, čo by sa stalo, keby sme mali v tabuľke nejaký štvorec, kde B a C by boli ofarbené rôzne (napr. B na bielo a C na čierno).
\displaystyle\begin{matrix}A & B \\C & D\end{matrix}
Potom existuje cesta, ktorá vedie z ľavého horného rohu cez A, B, D do pravého dolného rohu. Keď nahradíme políčko B políčkom C, tak dostaneme tiež platnú cestu, ale bude mať o jedno čierne políčko viac, čo je spor. Takýto štvorec teda nemôže existovať, preto musí byť v každej uhlopriečke len jedna farba.
Uhlopriečok je 2n - 1 a každú z nich môžeme nezávisle ofarbiť jednou z dvoch farieb, takže máme 2^{2n - 1} možných ofarbení.