5. Zadatak

Prvo rješenje.

Za raspored kutija ćemo reći da je dobar ako Fiko može krenuti s prve kutije u nizu i skočiti redom na svaku iduću kutiju.

Neka je $a_n$ traženi broj dobrih rasporeda kutija za prirodni broj $n$.

Za svaki dobar raspored $n$ kutija uklanjanjem najviše kutije dobivamo dobar raspored $n-1$ kutija.

Obratno, ako je dan dobar raspored kutija visina $1,2,\ldots,n-1$, onda kutiju visine $n$ možemo dodati na točno dva mjesta kako bismo i dalje dobili dobar raspored: možemo ju dodati na početak niza ili točno iza kutije visine $n-1$.

Stoga je $a_n=2a_{n-1}$.

Iz toga slijedi da je

$$a_n=2a_{n-1}=2^2a_{n-2}=\cdots=2^{n-1}a_1.$$

Budući da je $a_1=1$, zaključujemo da je $a_n=2^{n-1}$.

Drugo rješenje.

Za raspored kutija ćemo reći da je dobar ako Fiko može krenuti s prve kutije u nizu i skočiti redom na svaku iduću kutiju. Kutiju visine $n$ ćemo jednostavno zvati kutija $n$.

Neka je $a_n$ traženi broj dobrih rasporeda kutija za prirodni broj $n$. Očito je $a_1=1$.

Kako bismo odredili vrijednost $a_n$, razmotrimo gdje se sve može nalaziti najviša kutija.

Kutiju $n$ uvijek možemo staviti na prvo mjesto, bez obzira na raspored preostalih kutija. Naime, Fiko s nje može skočiti na bilo koju drugu kutiju, budući da su sve ostale niže od $n$. Dakle, za svaki mogući dobri raspored $n-1$ kutija dobijemo jedan dobri raspored $n$ kutija u kojemu je kutija $n$ na prvom mjestu.

Pretpostavimo da se kutija $n$ nalazi na drugom mjestu. Primijetimo da tada na prvom mjestu mora biti kutija $n-1$; u suprotnom mačak Fiko nikako ne može s prve kutije skočiti na drugu. Dakle, za svaki mogući dobri raspored $n-2$ kutija dobijemo jedan dobri raspored $n$ kutija u kojemu je kutija $n$ na drugom mjestu.

Analogno, ako se kutija $n$ nalazi na $k$-tom mjestu, gdje je $k\in\{3,4,\ldots,n\}$, onda se na mjestu $k-1$ mora nalaziti kutija $n-1$, na mjestu $k-2$ kutija $n-2$, itd. na mjestu $1$ kutija $n-k+1$. Preostalih $n-k$ kutija možemo poredati u bilo koji od $a_{n-k}$ dobrih rasporeda.

Stoga vrijedi

$$a_n=a_{n-1}+a_{n-2}+a_{n-3}+\cdots+a_1+1.$$

Budući da je $a_1=1$, sada možemo računati $a_2=2$, $a_3=2+1+1=4$ i postavljamo slutnju da je $a_n=2^{n-1}$.

Tu tvrdnju dokazujemo matematičkom indukcijom. Bazu već imamo, a ako pretpostavimo da je $a_k=2^{k-1}$ za sve $k<n$, prema dobivenoj rekurzivnoj relaciji slijedi

$$a_n=2^{n-2}+2^{n-3}+2^{n-4}+\cdots+2^0+1=2^{n-1}.$$

Treće rješenje.

Primijetimo da pozicija najviše kutije, tj. kutije $n$, jedinstveno određuje raspored kutija lijevo od nje. Naime, ispred kutije $n$ može biti jedino kutija $n-1$, a ispred nje onda jedino kutija $n-2$ itd.

Za preostale kutije možemo razmišljati na isti način. Preciznije, neka se kutija $n$ nalazi na poziciji $k\in\{1,2,\ldots,n\}$. To znači da točno znamo raspored kutija $n-1,n-2,\ldots,n-k+1$. Preostalih $n-k$ kutija se nalazi na pozicijama $k+1,k+2,\ldots,n$ i one su raspoređene po istom pravilu.

Pridružimo svakom rasporedu $n$ kutija $n$-znamenkasti binarni niz kojemu je na zadnjem mjestu uvijek $1$.

Svako mjesto s kojeg Fiko mora skočiti dolje označimo s $1$, a svako gdje mora skočiti gore s $0$.

Vrijedi i obratno, svaki takav binarni niz odgovara točno jednom rasporedu kutija po kojima Fiko može skakati. Prva jedinica u tom nizu određuje poziciju kutije visine $n$. Kao što smo vidjeli, sve kutije lijevo od te pozicije su onda jedinstveno određene. Druga jedinica neka određuje mjesto najviše kutije od preostalih, i tako dalje.

Na slici je primjer koji odgovara binarnom nizu $0\ 1\ 0\ 0\ 1\ 0\ 1\ 1\ 0\ 1$.

Dakle, traženih rasporeda kutija ima jednako kao i binarnih nizova duljine $n$ kojima je na zadnjem mjestu $1$, odnosno ima ih $2^{n-1}$.