5. Zadatak

Uočimo da je $1,2,\ldots,n-1,n,1,2,\ldots,n-1,n$ jedan dobar raspored. Za taj raspored možemo na $n+1$ način ukloniti $n$ kartica tako da preostanu brojevi $1$ do $n$ slijeva nadesno (uklanjamo bilo kojih $n$ uzastopnih kartica). Za svaki drugi dobar raspored moraju preostati neke kartice iz prvog kompleta i neke kartice iz drugog.

Promotrimo jedan takav dobar raspored kartica. Neka je $k$ najveći broj koji preostane na stolu iz prvog kompleta, tj. neka su iz prvog kompleta preostale kartice s oznakama od $1$ do $k$, a iz drugog kompleta od $k+1$ do $n$. Broj $k$ može biti bilo koji prirodan broj za koji vrijedi $k<n$.

Budući da su oba kompleta bila posložena u istom poretku, u prvom kompletu su kartice od $k+1$ do $n$ također morale biti u rastućem poretku slijeva nadesno. Dakle, poredak kartica u prvom kompletu (pa onda i u drugom kompletu) se sastoji od dva rastuća niza - jedan je od $1$ do $k$, a drugi od $k+1$ do $n$.

Zamislimo da su kartice na kojima su oznake od $1$ do $k$ crvene, a preostale kartice plave. Broj $k$ i raspored kartica je jednoznačno određen jednom kad za kartice prvog kompleta odaberemo koje su crvene, a koje plave. Pritom su svi rasporedi boja dopušteni, osim da su sve kartice iste boje ili da se sve crvene kartice nalaze ispred svih plavih kartica jer bismo tada dobili raspored $1,2,\ldots,n-1,n,1,2,\ldots,n$.

Preostaje prebrojati na koliko načina možemo obojiti kartice na dopuštene načine. Svih mogućih bojenja ima $2^n$ jer za svaku karticu možemo odabrati jednu od dvije boje, ali točno $n+1$ bojenja nije dopušteno - ona bojenja u kojima je $k$ crvenih, pa $n-k$ plavih kartica za $k=0,1,2,\ldots,n$.

Kad uračunamo još i dobar raspored $1,2,\ldots,n-1,n,1,2,\ldots,n-1,n$, zaključujemo da je broj dobrih rasporeda $2^n-n$.