5. Zadatak

Tvrdnju dokazujemo indukcijom po $n$.

Baza. Ako je $n=1$, na turniru su točno dva igrača. Prvi u nizu je pobjednik turnira (tj. njihovog međusobnog meča).

Korak. Pretpostavimo da tvrdnja vrijedi za neki prirodan broj $n$, tj. da među $2^n$ igrača koji su igrali svaki sa svakim možemo odabrati $n+1$ igrača i poredati ih u niz tako da je svaki od njih pobijedio sve igrače koji su iza njega u nizu.

Pobjednik turnira s $2^{n+1}$ igrača pobijedio je najmanje njih $2^n$.

Naime, ako bi svi igrači imali manje od $2^n$ pobjeda, onda bi ukupan broj pobjeda bio najviše $2^{n+1}\cdot(2^n-1)$. No znamo da je broj pobjeda jednak broju mečeva, što je

$$\frac12\cdot2^{n+1}\cdot(2^{n+1}-1)=2^n\cdot(2^{n+1}-1)>2^{n+1}\cdot(2^n-1).$$

Dakle, nemoguće je da su svi igrači imali manje od $2^n$ pobjeda.

Po pretpostavci, među $2^n$ igrača koje je pobjednik pobijedio možemo odabrati njih $n+1$ i poredati ih tako da je svaki od njih pobijedio sve igrače koji su iza njega. Pobjednika dodamo na početak i tako dobivamo traženi niz od $n+2$ igrača.