5. Zadatak

Dokazat ćemo da najmanji broj sjecišta koje Marko može postići iznosi $2$.

Označimo s $A_1,A_2,\ldots,A_{2022}$ redom vrhove danog mnogokuta.

Prvo navedimo primjer povlačenja crvenih dijagonala tako da se postignu točno dva sjecišta. Povucimo dijagonale $A_1A_3$ i $A_2A_4$, koje se sijeku. Nakon toga povlačimo međusobno paralelne dijagonale

$$A_{2022}A_5,A_{2021}A_6,\ldots,A_{1011}A_{1016}.$$

Konačno, povucimo još dijagonale $A_{1012}A_{1014}$ i $A_{1013}A_{1015}$ koje se međusobno sijeku. Time dobivamo primjer s ukupno $2$ sjecišta.

Dokažimo da uvijek imamo najmanje dva sjecišta. Pretpostavimo suprotno, postoji primjer povlačenja dijagonala u kojem imamo najviše jedno sjecište, te promotrimo taj primjer.

Promotrimo dvije točke $A_i,A_j$ koje nisu susjedne niti suprotne, tj. da ne vrijedi ni $|i-j|=1$ ni $|i-j|=1011$. Reći ćemo da se neka točka $A_k$ nalazi između $A_i$ i $A_j$ ako se nalazi u manjem od dva dijela mnogokuta kojeg određuje pravac $A_iA_j$.

Među svim dijagonalama koje je Marko povukao odaberimo onu koja povezuje vrhove između kojih ima najmanje drugih vrhova - reći ćemo da je to najkraća dijagonala. Bez smanjenja općenitosti, ta dijagonala je oblika $A_1A_k$, gdje je $k\leq1012$.

Promotrimo točke $A_2,\ldots,A_{k-1}$. One su krajnje točke dijagonala koje povezuju vrhove između kojih ima više od ili jednako mnogo drugih vrhova kao za dijagonalu $A_1A_k$, stoga je svaka ta točka krajnja točka neke dijagonale koja siječe dijagonalu $A_1A_k$. Kako u mnogokutu imamo najviše jedno sjecište, zaključujemo da je nužno $k=3$, te dijagonala $A_1A_k$ presijeca dijagonalu $A_2A_m$, za neki indeks $m$. Bez smanjenja općenitosti, $m\leq1013$.

Dokažimo da je $m=4$. Pretpostavimo da je $m\geq5$. Sve dijagonale kojima je jedna krajnja točka u skupu $\{A_4,A_5,\ldots,A_{m-1}\}$ nužno imaju i drugu točku u tom skupu. Inače bi ta dijagonala sjekla dijagonalu $A_2A_m$. Među svim takvim dijagonalima odaberimo najkraću: neka je to $A_kA_l$. Slično kao ranije, svi vrhovi između $A_k$ i $A_l$ krajevi su dijagonala koje nisu kraće od dijagonale $A_kA_l$, pa ju nužno siječe, čime dobivamo dva sjecišta. Dakle, nužno je $m=4$.

Izaberimo ponovno najkraću dijagonalu u mnogokutu, različitu od $A_1A_3$ i $A_2A_4$: neka je to $A_kA_l$. Ako između točaka $A_k$ i $A_l$ postoji neka točka različita od $A_1,A_2,A_3$ i $A_4$, moći ćemo ponovno zaključiti da postoji neka dijagonala koja siječe $A_kA_l$. Zato zaključujemo da je dijagonala $A_kA_l$ upravo $A_{2022}A_5$.

Ovaj argument možemo ponoviti: sljedeća najkraća dijagonala u mnogokutu je $A_{2021}A_6$, pa $A_{2020}A_7$, i redom sve do $A_{1519}A_{508}$. Posljednja dijagonala je dijagonala koja spaja suprotne vrhove mnogokuta, stoga je to najduža moguća dijagonala. Kako je iz konstrukcije to do tog trenutka najkraća dijagonala, zaključujemo da su sve preostale dijagonale jednake duljine, tj. da spajaju suprotne vrhove mnogokuta. No, sve takve dijagonale prolaze središtem mnogokuta, čime dobivamo još barem jedno sjecište. To je u suprotnosti s pretpostavkom da Marko može povući dijagonale tako da postoji najviše jedno sjecište dijagonala.

Zaključujemo da je zaista najmanji broj sjecišta dijagonala jednak $2$.