Sakrij rješenje
Neka je prirodan broj veći od
. Na kružnici je
jednako udaljenih točaka od kojih je točno
obojano crveno. Takvo bojanje zovemo
ako postoji barem jedan par crvenih točaka takvih da se unutar jednog luka koji taj par tvori nalazi točno
točaka. Odredi najmanji mogući
za koji je svako bojanje točaka na kružnici
.
Kliknite ovdje kako biste prikazali rješenje.
Umjesto dobrih gledat ćemo loša bojanja koja definiramo kao sva bojanja koja nisu dobra.
Neka je maksimalan broj točaka koje loše bojanje može imati. Dakle
tj. tražimo
.
Označit ćemo vrhove sa . Spojimo svaki par
i
promatrajući indekse modulo
. Bojanje je loše ako i samo ako su
crvena vrha spojena tetivom. Ako se krenemo tetivama "kretati" u jednom smjeru iz vrha u vrh te se u nekom trenutku vratimo na isti vrh to zovemo ciklusom. Tih ciklusa u ovom slučaju ima
, gdje
predstavlja najveći zajednički djelitelj brojeva
i
.
Primjenom Euklidovog algoritma dobivamo da je Dakle ako je
djeljivo s
, onda je
ciklusa, inače je samo
. Ako je samo
ciklus očito je
.
Ako je pak ciklusa koji svaki sadrži
vrha, svaki ciklus može imati maksimalno
crvenih točaka u lošem bojanju.
Dakle, u ovom slučaju