5. Zadatak

Prvo rješenje.

Tvrdnja zadatka vrijedi za sve neparne prirodne brojeve $n$.

Dokažimo prvo da tvrdnja ne vrijedi ni za jedan paran $n$. Dovoljno je naći jedan uredno povezan arhipelag s $n$ otoka koji ima neparan broj avionskih linija. Promotrimo arhipelag u kojemu su sve linije iz točno jednog istaknutog otoka avionske, a sve preostale brodske.

Jasno je da je broj avionskih linija neparan. Nadalje, za svako kružno putovanje vrijedi da je broj avionskih linija na tom putovanju jednak dvostrukom broju prolaska kroz taj istaknuti otok (budući da svakim dolaskom na otok, koji se odvija avionskom linijom, s otoka moramo i otići ponovno avionskom linijom). Posebno, svako kružno turističko putovanje sadrži paran broj avionskih linija, pa smo našli primjer uredno povezanog arhipelaga s neparnim brojem avionskih linija.

Sada dokažimo da za neparne $n$ tvrdnja vrijedi. Promotrimo bilo koji uredno povezan arhipelag s $n$ otoka. Promotrimo otoke kao vrhove pravilnog $n$-terokuta s vrhovima $A_1$, $A_2$, $\ldots$, $A_n$. Avionske i brodske linije su tada neke stranice ili dijagonale tog $n$-terokuta.

Za svaki $1\leq k\leq n-1$ definirajmo $S_k$ kao skup dužina

$$\overline{A_1A_{k+1}},\ \overline{A_2A_{k+2}},\ \ldots,\ \overline{A_{n-k}A_n},\ \overline{A_{n-k+1}A_1},\ \ldots,\ \overline{A_nA_k}.$$

Prvo primijetimo da su sve gore popisane dužine različite. Uistinu, ako je gore dvaputa navedena dužina $A_iA_j$, uz $i<j$, zbog $j-i=k$ i $i-j=n-k$ vrijedi da je $n=2k$. Kako je $n$ neparan, to nije moguće.

Svaki vrh $n$-terokuta ima točno dvije dužine kojima je taj vrh krajnja točka, a pripadaju skupu $S_k$.

To znači da linije reprezentirane dužinama u skupu $S_k$ čine jedno kružno putovanje (ako su $k$ i $n$ relativno prosti) ili nekoliko kružnih putovanja jednake duljine (ako $k$ i $n$ nisu relativno prosti). Kako duž svakog kružnog putovanja imamo paran broj avionskih linija, zaključujemo da se u skupu $S_k$ nalazi paran broj dužina koje odgovaraju avionskim linijama.

Nadalje, promotrimo li sve skupove $S_k$, vidimo da se svaka dužina nalazi u točno jednom skupu $S_k$. Kako u svakom $S_k$ se nalazi paran broj avionskih linija, i ukupan broj avionskih linija u arhipelagu je paran, čime je dokaz gotov.

Drugo rješenje.

Kao u prvom rješenju dokažemo da tvrdnja ne vrijedi ni za koji paran $n$.

Dokažimo da tvrdnja vrijedi za neparne $n$. Promotrimo bilo koji uredno povezan arhipelag s $n$ otoka i dokažimo da nužno ima paran broj avionskih linija.

Promotrimo neki otok $x$. Neka je $B$ skup svih otoka koji su s $x$ povezani brodskom linijom, a $A$ skup svih otoka koji su s $x$ povezani avionskom linijom.

Prvo primijetimo da su svi otoci unutar $B$ međusobno povezani brodskom linijom. Tvrdnja je trivijalna ako se u $B$ nalazi manje od dva otoka. Ako je u $B$ dva ili više otoka, tada promotrimo kružno putovanje koje povezuje bilo koja dva otoka iz $B$ i otok $x$. Dvije veze od tri su brodske, pa kako bi bilo parno mnogo avionskih linija u tom putovanju, i treća veza mora biti brodska.

Slično dokažemo da su i svi otoci unutar $A$ međusobno povezani brodskom linijom: kako kružno putovanje koje povezuje bilo koja dva otoka iz $A$ i otok $x$ ima paran broj avionskih linija, nužno je veza između dva otoka iz $A$ brodska (jer su svi otoci iz $A$ s $x$ povezani avionskom linijom).

Konačno, uzmimo proizvoljni otok $a$ iz $A$ i proizvoljni otok $b$ iz $B$. Tada su na kružnom putovanju koje uključuje tri otoka $x$, $a$ i $b$ jedna brodska linija, jedna avionska linija te linija između $a$ i $b$. Iz uvjeta uredne povezanosti, zaključujemo da ona mora biti avionska.

Uvedimo oznaku $\widetilde{B}:=B\cup\{x\}$. Neka je $m$ broj otoka u skupu $A$, te $n-m$ broj otoka u skupu $\widetilde{B}$. Upravo smo zaključili da su sve linije između otoka u $\widetilde{B}$ brodske, te su sve linije između otoka u $A$ brodske. Dakle, sve avionske linije su samo one koje povezuju svaki otok iz $\widetilde{B}$ sa svakim otokom iz $A$. Broj takvih linija je $m(n-m)$.

Kako je $n$ neparan, barem jedan od faktora $m$ ili $n-m$ je paran, pa je i njihov umnožak paran. Dakle, broj avionskih linija u arhipelagu je paran.