5. Zadatak
U računalnoj igrici Smješko mora doći od starta do cilja krećući se u smjeru istoka ili juga po stranicama zadane mreže. Mreža se sastoji od jednakih kvadrata, a duljina stranice tog kvadrata iznosi jedan korak. (Npr. od starta do cilja može doći krećući se koraka na istok pa koraka na jug). Na koliko načina Smješko može doći do cilja? Obrazloži odgovor.
Prvo rješenje.
Kretanje za jedan korak u smjeru istoka kratko ćemo označavati s I, a kretanje za jedan korak u smjeru juga kratko ćemo označavati s J.
Označimo sve vrhove kvadrata s točkama. Iz svake točke Smješko može ići prema istoku ili jugu, a broj pored točke neka broji različite načine kretanja od tog mjesta do cilja.
Točkama iz kojih postoji samo mogući put do cilja pridružit ćemo broj .
Promatrajmo kvadrat u donjem desnom uglu. Iz posljednje neoznačene točke do cilja možemo doći na načina (IJ, JI). Stoga toj točki pridružujemo broj .
Iz točke iznad točke koji smo pridružili broj možemo do cilja doći na načina (IJJ, JIJ, JJI). Stoga njoj pridružujemo broj .
Isto vrijedi i za točku lijevo od točke kojoj smo pridružili broj . Iz nje također postoje načina dolaska do cilja (IIJ, IJI, JII).
Zaključujemo da se za vrijednost pridružena svakoj pojedinoj točki dobije tako da zbrojimo vrijednosti točaka koje se nalaze jedno mjesto prema istoku i jedno mjesto prema jugu.
Popunjavanjem mreže imamo sljedeću sliku.
Dakle, mogući broj načina da Smješko dođe od starta do cilja je .
Drugo rješenje.
Kretanje za jedan korak u smjeru istoka kratko ćemo označavati s I, a kretanje za jedan korak u smjeru juga kratko ćemo označavati s J.
Svako kretanje od starta do cilja završava u koraka. Razmotrimo posebno mogućnost prvog koraka prema jugu i prvog koraka prema istoku.
Ako krenemo prvim korakom na jug, drugi korak može biti na istok ili jug. I tako redom dok ne dođemo sasvim na istok (onda može samo na jug) ili sasvim na jug (onda može samo na istok).
Prikazat ćemo kretanje grafički tako da odaberemo prva tri koraka.
Ako krenemo korak prema jugu pa korak prema istoku (JI) do cilja možemo stići na različitih načina.
Ako krenemo dva koraka prema jugu pa korak prema istoku (JJI) isto je kao da smo krenuli korak prema jugu, korak prema istoku pa opet prema jugu (JIJ) pa do cilja možemo stići na različitih načina.
Ako krenemo tri koraka prema jugu (JJJ) imamo sljedećih mogućnosti:
Time dolazimo do cilja na različitih načina krenemo li prvim korakom prema jugu.
Ako krenemo prvim korakom na istok, drugi korak može biti na istok (II) ili jug (IJ).
Ako krenemo korak prema istoku pa korak prema jugu (IJ) isto je kao da smo krenuli korak prema jugu, korak prema istoku (JI) pa do cilja možemo stići na različitih načina.
Ako krenemo dva koraka prema istoku pa korak prema jugu (IIJ) isto je kao da smo krenuli korak prema jugu pa dva koraka prema istoku (JII) pa do cilja možemo stići na različitih načina.
Preostaje još samo kretanje koraka prema istoku i koraka prema jugu.
Time dolazimo do cilja na različiti način krenemo li prvim korakom prema istoku.
Ukupno je različitih mogućnosti kretanja Smješka od starta do cilja.
Treće rješenje.
Kretanje za jedan korak u smjeru istoka kratko ćemo označavati s I, a kretanje za jedan korak u smjeru juga kratko ćemo označavati s J.
Svako kretanje od starta do cilja završava u koraka. Nabrojimo sve mogućnosti.
Ako krenemo prvim korakom na jug do cilja možemo doći na različitih načina.
Ako krenemo prvim korakom na istok do cilja možemo doći na različiti način.
Ukupno je različitih mogućnosti kretanja Smješka od starta do cilja.
Četvrto rješenje.
Kretanje za jedan korak u smjeru istoka kratko ćemo označavati s I, a kretanje za jedan korak u smjeru juga kratko ćemo označavati s J.
Svako kretanje od starta do cilja završava u koraka.
Od toga je tri koraka na istok, a pet na jug.
Svaki takav put ćemo zapisati kao riječ od tri slova I i pet slova J.
Ako odredimo na kojim mjestima su slova I, onda su i slova J određena.
Za jedno slovo I možemo odabrati jedno od mjesta.
Za drugo slovo I možemo odabrati jedno od preostalih mjesta.
Za treće slovo I možemo odabrati jedno od preostalih mjesta.
To daje ukupno izbora.
Uočimo da smo tako previše puta brojali iste riječi.
Na primjer riječ JIJJIJI ima slovo I na , i mjestu, ali tu smo riječ mogli dobiti na šest načina ovisno o tome kojim redom smo upisivali slova I na ta mjesta (, , , , , ).
Svaka riječ se dobiva na načina, pa je zato broj različitih riječi
Ukupno je različitih mogućnosti kretanja Smješka od starta do cilja.