5. Zadatak

Najmanji takav $k$ je

$$K:=\frac{n}{2}\quad\text{za parne }n, \qquad\text{odnosno}\qquad K:=\frac{n+1}{2}\quad\text{za neparne }n.$$

Pretpostavimo prvo da je crvenom bojom obojeno manje od $K$ vrhova. Tada je neobojenih vrhova strogo više nego crvenih, te sigurno postoje dva susjedna neobojena vrha.

S obzirom na to da u svakoj triangulaciji stranica mnogokuta koja spaja ta dva neobojena vrha mora biti dio nekog trokuta, zaključujemo da taj trokut ima barem dva neobojena vrha, odnosno sigurno ima najviše jedan crveni vrh.

Preostaje pronaći primjer bojenja i odabira dijagonala u slučaju kada je barem $K$ vrhova obojeno crveno te postoji barem jedna dobra triangulacija.

Jedna mogućnost je da počevši od nekog vrha (koji obojimo) naizmjenično svaki sljedeći susjedni vrh ne obojimo, odnosno obojimo. Tada sigurno ne postoje dva susjedna neobojena vrha.

Odaberimo proizvoljan crveni vrh $C$ i povucimo iz njega svih $n-3$ dijagonala. Tada svaki trokut u toj triangulaciji za vrhove ima $C$ i neka dva susjedna vrha mnogokuta. Zbog načina bojenja znamo da je barem jedan od ta dva vrha crvene boje, pa svaki trokut ima barem dva crvena vrha. Dakle, ta triangulacija je dobra, pa je $K$ najmanji broj $k$ koji zadovoljava uvjete zadatka.

Napomena: Oblik broja $K$ može se zapisati i kao $K=\left\lceil\frac{n}{2}\right\rceil$.