5. Zadatak

Označimo otoke u arhipelagu redom s $o_1,o_2,\ldots,o_{2026}$.

Za različite otoke $o_{i_1},o_{i_2},\ldots,o_{i_k}$ kažemo da čine ciklus duljine $k$ ako postoji brodska linija među otocima $o_{i_1}$ i $o_{i_2}$, $o_{i_2}$ i $o_{i_3}$, $\ldots$, $o_{i_{k-1}}$ i $o_{i_k}$ te među otocima $o_{i_k}$ i $o_{i_1}$. Trebamo odrediti najveći prirodan broj $N$ takav da, neovisno o rasporedu brodskih linija, uvijek postoji ciklus duljine $N$.

Promotrimo raspored brodskih linija takav da su svi otoci $o_1,o_2,\ldots,o_{1013}$ međusobno povezani brodskim linijama, svi otoci $o_{1014},o_{1015},\ldots,o_{2026}$ su također međusobno povezani brodskim linijama te među otocima $o_i$ i $o_j$ nema brodske linije za sve $1\leq i\leq1013$ i $1014\leq j\leq2026$. Takav raspored očito zadovoljava uvjet zadatka te u tom slučaju najveća duljina ciklusa iznosi točno $1013$. Dakle, vrijedi $N\leq1013$.

Dokažimo da uvijek postoji ciklus duljine barem $1013$, neovisno o rasporedu brodskih linija.

Pretpostavimo da u arhipelagu postoje neka tri otoka među kojima nema brodske linije. Bez smanjenja općenitosti možemo pretpostaviti da su to otoci $o_1,o_2$ i $o_3$.

Promotrimo tada pet otoka $o_1,o_2,o_3,o_i$ i $o_j$ pri čemu je $3<i<j$. Iz uvjeta zadatka slijedi da tada među otocima $o_i$ i $o_j$ postoji brodska linija za sve $3<i<j$. Dakle, svi otoci $o_4,o_5,\ldots,o_{2026}$ su međusobno povezani brodskim linijama te u tom slučaju postoji ciklus duljine $2023$.

Pretpostavimo sada da među svaka tri otoka postoje dva koja su povezana brodskom linijom.

Za otoke $o_{i_1},o_{i_2},\ldots,o_{i_k}$ kažemo da čine put duljine $k$ ako postoji brodska linija među otocima $o_{i_1}$ i $o_{i_2}$, $o_{i_2}$ i $o_{i_3}$, $\ldots$, $o_{i_{k-1}}$ i $o_{i_k}$.

Neka je $k$ duljina najduljeg puta u arhipelagu. Bez smanjenja općenitosti možemo pretpostaviti da otoci $o_1,o_2,\ldots,o_k$ čine put duljine $k$.

Ako je $k=2026$, promotrimo otoke $o_1,o_{1013}$ i $o_{2026}$. Budući da među svaka tri otoka postoje dva koja su povezana brodskom linijom, slijedi da će $o_1$ biti povezan s $o_{1013}$, $o_1$ biti povezan s $o_{2026}$ ili će $o_{1013}$ biti povezan s $o_{2026}$. U svakom od ta tri slučaja postoji ciklus duljine barem $1013$.

Ako je $k<2026$, označimo sa $S$ skup svih otoka $o_i$ za $i>k$. Kako je $k<2026$, znamo da skup $S$ nije prazan.

Uočimo da zbog maksimalnosti broja $k$ slijedi da otoci $o_1$ i $o_k$ nisu povezani niti s jednim otokom u skupu $S$.

Posebno, kako otoci $o_1$ i $o_k$ nisu povezani s otokom $o_{k+1}$, slijedi da tada mora postojati brodska linija između $o_1$ i $o_k$. Dakle, otoci $o_1,o_2,\ldots,o_k$ čine ciklus.

Nadalje, za svaka dva različita otoka $o_i$ i $o_j$ iz $S$ vrijedi da su međusobno povezani brodskom linijom jer otoci $o_i$ i $o_j$ nisu povezani s otokom $o_1$. Prema tome, svi otoci u skupu $S$ su međusobno povezani brodskim linijama, pa u skupu $S$ postoji put duljine $2026-k$.

Budući da je $k$ duljina najduljeg puta, slijedi da mora biti $k\geq2026-k$, odnosno $k\geq1013$.

Kako otoci $o_1,o_2,\ldots,o_k$ čine ciklus, zaključujemo da i u ovom slučaju postoji ciklus duljine barem $1013$.

Zaključujemo da je $N\geq1013$, odnosno $N=1013$.