5. Zadatak

Prvo rješenje.

Odredimo najprije broj puteva u kojima je prvi pomak desno. Budući da se putevi u kojima je prvi korak gore dobivaju na simetričan način, ukupan broj puteva ćemo dobiti množenjem dobivenog broja s $2$.

Neka su $x$ i $y$ duljine prvog i drugog pomaka gore pri čemu je $x,y\in\mathbb N$. Duljine prvog, drugog i trećeg pomaka desno označimo sa $a$, $b$, $c$ pri čemu je $a,b,c\in\mathbb N$.

Tada je:

$$x+y=8$$ $$a+b+c=8$$

Promotrimo broj uređenih parova $(x,y)$ i broj uređenih trojki $(a,b,c)$ kojima se mogu opisati svi različiti načini kojima mrav može doći od točke $P$ do točke $K$.

Uređeni parovi $(x,y)$ za koje je $x+y=8$ su $(1,7)$, $(2,6)$, $(3,5)$, $(4,4)$, $(5,3)$, $(6,2)$, $(7,1)$. Njihov je broj $7$.

Ispišimo sva rješenja jednadžbe $a+b+c=8$, redom, prema vrijednosti varijable $a$.

• Ako je $a=1$, tada imamo $6$ uređenih trojki: $(1,1,6)$, $(1,2,5)$, $(1,3,4)$, $(1,4,3)$, $(1,5,2)$, $(1,6,1)$.
• Ako je $a=2$, tada imamo $5$ uređenih trojki: $(2,1,5)$, $(2,2,4)$, $(2,3,3)$, $(2,4,2)$, $(2,5,1)$.
• Ako je $a=3$, tada imamo $4$ uređene trojke: $(3,1,4)$, $(3,2,3)$, $(3,3,2)$, $(3,4,1)$.
• Ako je $a=4$, tada imamo $3$ uređene trojke: $(4,1,3)$, $(4,2,2)$, $(4,3,1)$.
• Ako je $a=5$, tada imamo $2$ uređene trojke: $(5,1,2)$, $(5,2,1)$.
• Ako je $a=6$, tada imamo $1$ uređenu trojku: $(6,1,1)$.

Takvih je uređenih trojki ukupno $6+5+4+3+2+1=21$.

Broj različitih načina na koje mrav može doći od točke $P$ do točke $K$, ako je prvi pomak desno, dobit ćemo tako da pomnožimo broj uređenih parova i broj uređenih trojki tj. $7\cdot21=147$.

Stoga je broj različitih načina na koje mrav može doći od točke $P$ do točke $K$ na opisani način jednak $294$.

Drugo rješenje.

Neka je točka $P$ ishodište koordinatnog sustava, $P(0,0)$. Na svom putu do točke $K(8,8)$ mrav mora promijeniti smjer u točno $4$ točke. Označimo te točke, redom, $S_1$, $S_2$, $S_3$ i $S_4$.

Odredimo najprije broj puteva u kojima je prvi pomak desno. Budući da se putevi u kojima je prvi korak gore dobivaju na simetričan način, ukupan broj puteva ćemo dobiti množenjem dobivenog broja s $2$.

Apscise točaka $S_1(x_1,0)$ i $S_3(x_3,y_3)$ su, tada, $1\le x_1<x_3\le7$ pa ih možemo odabrati na $\frac{7\cdot6}{2}=21$ različit način.

Točke $S_1$ i $S_2$ imaju jednake apscise, $x_1=x_2$. Za jednom odabranu točku $S_1$, točki $S_2(x_2,y_2)$ ordinata je $1\le y_2\le7$ pa se može odabrati na $7$ različitih načina.

Za jednom odabrane točke $S_1$, $S_2$ i $S_3$, točka $S_4$ je već određena, $S_4(x_3,8)$.

Broj različitih načina na koje mrav može doći od točke $P$ do točke $K$, ako je prvi pomak desno, dobit ćemo tako da pomnožimo broj odabira apscisa točaka $S_1$ i $S_3$ te broj odabira ordinate točke $S_2$, tj.

$$7\cdot21=147.$$

Stoga je broj različitih načina na koje mrav može doći od točke $P$ do točke $K$ na opisani način jednak $294$.