Grade 10 2021 Problem 5

Neka je $n$ prirodni broj. Ako pravilan $n$-terokut podijelimo na $n-2$ trokuta povlačenjem $n-3$ dijagonala koje nemaju zajedničkih unutarnjih točaka kažemo da smo dobili triangulaciju. Triangulacija $n$-terokuta kojem su neki od vrhova crveni je dobra ako svaki od tih $n-2$ trokuta ima barem dva crvena vrha.

Odredi najmanji prirodni broj $k$, u ovisnosti o $n$, takav da možemo obojiti $k$ vrhova pravilnog $n$-terokuta crveno tako da postoji barem jedna dobra triangulacija.