Výsledok:
Keďže Nate má iba päť kried, cesta sa nikdy nemôže pohybovať na juh ani na západ – každá krieda okrem prvej vie súradnice koncového políčka zvýšiť maximálne o (a prvá o ), pričom my sa potrebujeme dostať z políčka do políčka . Koniec cesty sa teda vždy posúva iba na sever alebo na východ.
Počet ciest určíme postupným vypĺňaním tabuľky nasledovným spôsobom: do každého políčka zapíšeme počet ciest do tohto políčka z kried, ktorých posledné okrajové políčko leží práve v tomto políčku. Po položení prvej kriedy z ľavého dolného rohu musí byť jej koniec presne o dve políčka ďalej: buď dve doprava (vodorovná krieda), alebo dve hore (zvislá krieda). Preto do políčok a zapíšeme číslo . Zvyšok tabuľky vyplníme postupne smerom k pravému hornému rohu. Ak chceme určiť hodnotu v políčku , uvažujeme, akými spôsobmi tam môže krieda končiť. Krieda končiaca v môže byť zvislá alebo vodorovná a v oboch prípadoch sa musí dotýkať predchádzajúcej kriedy okrajovým políčkom. Dostávame štyri možné okrajové políčka predchádzajúcej kriedy – a v prípade zvislej kriedy a a v prípade vodorovnej kriedy.
Každé z týchto políčok predstavuje korektný spôsob, ako predĺžiť existujúcu cestu o jednu kriedu. Preto do políčka zapíšeme súčet hodnôt v políčkach , pričom políčka mimo mriežky prispievajú hodnotou .
Po vyplnení celej tabuľky dostaneme v pravom hornom rohu číslo , čo je presne počet všetkých platných ciest z kried z ľavého dolného do pravého horného rohu.
Iné riešenie. Položme päť kried za sebou od rohu tak, že sa navzájom dotýkajú iba v rohoch (roh koncového políčka jednej kriedy s rohom koncového políčka nasledujúcej). Každá krieda posunie okrajové políčko buď o („hore“), alebo o („doprava“). Po piatich kriedach je okrajovým políčkom políčko s vlastnosťou .
Nech je počet zvislých kried a počet vodorovných kried. Potom a
|
Aby sme z reťaze dotýkajúcej sa iba v rohoch dostali korektnú cestu, kde sa susedné kriedy dotýkajú celou hranou, musíme „opraviť“ každý zo štyroch spojov medzi po sebe idúcimi kriedami. Pri každom spoji si zvolíme jednu z dvoch možností: buď posunieme celý zvyšok cesty (od nasledujúcej kriedy až po piatu) o jedno políčko doľava, alebo o jedno políčko nadol. Tak zabezpečíme, že dve susedné kriedy budú mať spoločnú hranu namiesto spoločného rohu.
Nech je počet spojov, pri ktorých zvolíme posun doľava, a počet spojov s posunom nadol. Keďže sú presne štyri spoje, platí . Po vykonaní všetkých posunov sa okrajové políčko presunie na . Aby sme dostali cestu z do pravého horného rohu , musí platiť .
Preskúmajme jednotlivé možnosti :
- : – Keďže , nedá sa opraviť na .
- : – Tiež sa nedá opraviť.
- : – Platí , (všetky posuny nadol). Existuje spôsobov, ako zoradiť kriedy rôznych orientácii za seba, no potom pre každé zoradenie iba 1 spôsob opravy, spolu ciest.
- : – Platí , . Existuje spôsobov, ako zoradiť kriedy a pre každé zoradenie spôsobov, ako vybrať, kde budú posuny doľava, spolu ciest.
- : – Platí , (všetky posuny doľava). Existuje zoradení kried a jediný spôsob opravy, spolu ciest.
- : – Ani toto sa nedá opraviť.
Celkovo teda dostaneme ciest.