5. Zadatak

Prvo rješenje.

Neka je $A_n$, odnosno $B_n$, broj svih mogućih poredaka $n$ biciklista na kraju utrke u kojoj je svaki biciklist pretjecao točno, odnosno najviše, jednom. Označimo bicikliste na početku utrke brojevima od $1$ do $n$.

Prvo promotrimo poredak na kraju utrke u kojoj je svaki biciklist pretjecao najviše jednom. Biciklist s oznakom $n$ može biti na zadnjem ili predzadnjem mjestu jer ne može pretjecati više nego jednom:

• ako je $n$ na zadnjem mjestu, onda taj poredak možemo dobiti tako da samo prvih $n-1$ biciklista pretječe – takvih poredaka ima $B_{n-1}$;
• ako je $n$ na predzadnjem mjestu, onda taj poredak možemo ostvariti i tako da $n$ pretječe u posljednjem pretjecanju, a prije toga su pretjecali samo neki od prvih $n-1$ biciklista – takvih poredaka ima $B_{n-1}$.

Time smo dokazali da je $B_n=B_{n-1}+B_{n-1}=2B_{n-1}$. Budući da je $B_2=2$, slijedi da je $B=B_{200}=2^{199}$.

Sada promotrimo poredak na kraju utrke u kojoj je svaki biciklist pretjecao točno jednom. Neka je $k$ najmanji broj takav da je biciklist $k+2$ pretjecao prije biciklista $k+1$. Tada konačni poredak mora biti $2,3,\ldots,k-1,1,k,x,\ldots,y$ jer je biciklist $k+2$ onemogućio miješanje biciklista s oznakama od $1$ do $k$ s biciklistima s oznakama većima od $k$, te je jedino moguće da su biciklisti od $1$ do $k$ pretjecali sljedećim redom: $2,3,\ldots,k,1$.

Time smo pokazali da je poredak određen odabirom broja $k$ (koji može biti bilo koji broj od $0$ do $n-2$) i poretkom oznaka od $k+1$ do $n$ (kojih ima kao i poredaka u utrci s $n-k$ biciklista, tj. $A_{n-k}$), pa vrijedi

$$A_n=A_{n-1}+A_{n-2}+\cdots+A_2+1.$$

Budući da je $A_2=1$, indukcijom lako pokazujemo da je $A_n=2^{n-2}$ za sve prirodne brojeve $n>1$. Zato je

$$2A=2A_{200}=2^{199}=B.$$

Drugo rješenje.

Dokazat ćemo tvrdnju direktno za utrke s $n$ biciklista. Svaki poredak biciklista odgovara permutaciji skupa $\{1,\ldots,n\}$. Svaka permutacija se može prikazati kao kompozicija permutacija u kojima točno dva elementa mijenjaju mjesto. Iako se svaka permutacija može prikazati na više različitih načina, poznat je rezultat da je parnost potrebnog broja takvih zamjena ista za sve moguće načine. Zato poredak možemo zvati paran, odnosno neparan, ako je dobiven parnim, odnosno neparnim, brojem pretjecanja.

Lema. Ako je neki poredak dobiven tako da je svaki biciklist s oznakama iz nekog podskupa $S\subseteq\{1,\ldots,n\}$ pretjecao točno jednom, te su $j$ i $k$ najmanje oznake koje nisu u $S$, onda isti poredak možemo dobiti tako da svaki biciklist iz skupa $S\cup\{j,k\}$ pretječe točno jednom.

Dokaz leme. Biciklisti su podijeljeni u tri grupe tako da biciklisti iz različitih grupa nisu mijenjali mjesto. Te grupe su $\{1,\ldots,j-1\}$, $\{j,\ldots,k-1\}$ i $\{k,\ldots,n\}$. Bilo koja dva pretjecanja u različitim grupama možemo raditi u bilo kojem poretku. Jasno je da ćemo u prvoj i trećoj grupi postići željeni raspored na isti način kao i bez pretjecanja biciklista $j$ i $k$.

Dakle, trebamo dokazati da poredak $j,\ldots,k-1,k$ koji se dobiva bez korištenja $j$ i $k$ možemo dobiti i korištenjem svih tih brojeva. Zbog ovoga, bez smanjenja općenitosti dovoljno je dokazati lemu za $j=1$ i $k=n$. Tu tvrdnju zovemo Tvrdnja 1.

Tvrdnja 2. Ako neki raspored možemo dobiti korištenjem svih pretjecanja osim $n$, onda taj isti raspored možemo dobiti tako da ne koristimo pretjecanje $1$, a koristimo pretjecanje $n$ (i sva ostala).

Tvrdnje 1 i 2 paralelno dokazujemo jakom indukcijom po $n$. Baza indukcije je trivijalna.

Pretpostavimo da tvrdnje 1 i 2 vrijede za sve brojeve manje od $n$. Za tvrdnju 1 imamo poredak koji smo dobili bez korištenja pretjecanja biciklista $1$ i $n$. Taj poredak nužno mora biti $2,3,\ldots,k-1,1,x,\ldots,y,n$, pri čemu $k$ može biti bilo koji broj od $0$ do $n$. Taj poredak možemo dobiti i tako da se prvo provedu sva pretjecanja od $2$ do $k-1$, pa onda dodamo novo pretjecanje biciklista $k$ i $1$, te konačno u nekom poretku pretjecanja svih biciklista od $k$ do $n$ koje daje traženi raspored prema pretpostavci za tvrdnju 2 (i za poredak $x,\ldots,y,n$).

Za tvrdnju 2 zaključujemo na sličan način. Imamo poredak u kojem je $n$ na kraju i $n$ nije pretjecao. Taj poredak nužno mora biti $2,3,\ldots,k-1,1,k,\ldots,n$. Bez smanjenja općenitosti možemo pretpostaviti da smo taj poredak dobili tako da su pretjecali biciklisti $2,3,\ldots,k-1,k$, pa $1$, pa svi ostali biciklisti osim $n$.

Sad opisujemo drukčiji način u kojem biciklist $1$ neće pretjecati, ali $n$ hoće. Prvo pretječu biciklisti $2,\ldots,k-1$, te nakon toga za bicikliste od $k$ do $n$ prema pretpostavci indukcije koristimo tvrdnju 1 (u početnom načinu smo promatrani poredak od $k$ do $n$ dobili bez pretjecanja biciklista $k$ jer je to pretjecanje bilo iskorišteno u zamjeni $k$ i $1$, i bez pretjecanja biciklista $n$, a novi način za isti poredak dozvoljava i $k$ i $n$). Time je dokaz leme gotov.

Lema pokazuje da se svaki poredak koji možemo dobiti tako da svaki biciklist pretječe najviše jednom možemo dobiti i s većim brojem pretjecanja iste parnosti (stalno dodajemo dvije najmanje oznake koje nemamo u skupu oznaka biciklista koji pretječu), tj. svi poretci su ili dobiveni s $n-1$ pretjecanja ili s $n$ pretjecanja. Broj poredaka dobivenih s $n$ pretjecanja je $A$.

Između poredaka dobivenih s $n$ pretjecanja i poredaka dobivenih s $n-1$ pretjecanja postoji bijekcija koja je dana izostavljanjem pretjecanja biciklista $n$. Zato je $B=2A$.