5. Zadatak

Prvo rješenje.

Promotrimo isti problem s ukupno $n$ omotnica te označimo s $K_n$ traženi broj rasporeda.

Neka je dan jedan raspored $n$ omotnica. Ako maknemo najmanju omotnicu, dobivamo raspored $n-1$ preostalih omotnica. S druge strane, ako nam je dan jedan mogući raspored preostalih $n-1$ omotnica, najmanju omotnicu možemo staviti u najveću omotnicu ili u bilo koju od preostalih $n-2$ omotnica. Dakle, $K_n$ je točno $n-1$ puta veći od $K_{n-1}$.

Stoga je

$$K_n=(n-1)\cdot K_{n-1}=(n-1)\cdot(n-2)\cdot K_{n-2}=\cdots=(n-1)\cdot(n-2)\cdots2\cdot K_2.$$

Kad imamo samo dvije omotnice, jedini mogući način je staviti manju unutar veće, pa je $K_2=1$.

Stoga je traženi broj rasporeda

$$K_n=(n-1)\cdot(n-2)\cdots1.$$

Za sto omotnica je broj različitih rasporeda $K_{100}=99\cdot98\cdots1$, tj. umnožak prvih 99 prirodnih brojeva.

Drugo rješenje.

Označimo najveću omotnicu brojem 1, drugu najveću brojem 2, treću najveću brojem 3, $\ldots$, a najmanju brojem 100. Zamislimo da je na početku omotnica s brojem 1 prazna i promotrimo na koje sve načine možemo preostale omotnice staviti u nju poštujući pritom uvjete zadatka.

U prvom koraku omotnicu 2 možemo na samo jedan način staviti u omotnicu 1. Zatim omotnicu 3 možemo staviti ili unutar omotnice 2 ili izvan omotnice 2, a unutar omotnice 1. Dakle, ukupno na dva načina. Općenito, omotnicu $k$ možemo staviti

• unutar omotnice $k-1$
• izvan omotnice $k-1$, a unutar omotnice $k-2$
• izvan omotnica $k-1$ i $k-2$, ali unutar omotnice $k-3$
• $\cdots$
• izvan svih ostalih omotnica osim omotnice 1.

To je ukupno $k-1$ načina.

Dakle, omotnice s brojevima 2, 3, $\ldots$, 100 možemo unutar omotnice 1 staviti na ukupno $1\cdot2\cdots99$ načina, što je ujedno i traženi broj rasporeda.