5. Zadatak

Obojimo polja ploče šahovski, tj. crnom i bijelom bojom tako da susjedna polja budu različite boje. (Ako je $1$ na bijelom, onda je $2n$ na crnom polju i obratno.)

Umjesto nizanja brojeva, razmišljajmo o povlačenju linije koja prolazi svakim poljem točno jednom. Vidjet ćemo da je linija zapravo određena svojim početnim poljem ($1$) i završnim poljem ($2n$).

Ako su krajevi linije oba u prvom ili oba u zadnjem stupcu, onda postoji točno jedna linija.

Ne postoji linija čiji su početak i kraj u istom stupcu koji nije na rubu ploče. U suprotnome bi linija morala samu sebe presjeći, tj. u neko polje ploče bismo upisali dva različita broja.

Neka su krajevi linije u različitim stupcima, recimo u stupcu $a$ i u stupcu $b$, pri čemu je $1\leq a<b\leq n$. S obzirom na to da linija mora proći kroz polja prvog stupca, određeno je kako prolazi stupcima od $1$ do $a$: od krajnje točke u stupcu $a$ ravno istim retkom do prvog stupca, i zatim drugim retkom do stupca $a$. Analogno vrijedi i za dio linije koji prolazi stupcima od $b$ do $n$.

Dio između stupaca $a$ i $b$ linija mora proći tako da prođe kroz oba polja stupca $a+1$, zatim oba polja stupca $a+2$ i tako dalje do stupca $b-1$. Dakle, za svaki odabir brojeva $a$ i $b$ imamo dvije linije kojima su krajevi u tim stupcima.

Prvo polje možemo odabrati na $2n$ načina, a zadnje polje može biti bilo koje od $n-1$ polja suprotne boje osim onoga u istom stupcu s prvim poljem.

Tako dobijemo $2n\cdot(n-1)$ linija.

Tom broju treba pridodati mogućnosti kada su krajnja polja u istom stupcu, prvom ili zadnjem. Za prvo polje postoje $4$ mogućnosti, a zadnje polje je onda ispod ili iznad njega. Stoga je konačno rješenje $2n(n-1)+4$.

Napomena: Nije nužno spominjati bojenje ploče. Dovoljno je uočiti da parni i neparni brojevi imaju određena mjesta u njoj.