Školjka

Umjesto dobrih gledat ćemo loša bojanja koja definiramo kao sva bojanja koja nisu dobra. Neka je $j$ maksimalan broj točaka koje loše bojanje može imati. Dakle $k=j+1$ tj. tražimo $j$. Označit ćemo vrhove sa $A_1,A_2,...,A_{2n-1}$. Spojimo svaki par $A_i$ i $A_{i+n+1}$ promatrajući indekse modulo $2n-1$. Bojanje je loše ako i samo ako su $2$ 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 $M(n+1, 2n-1)$, gdje $M(a,b)$ predstavlja najveći zajednički djelitelj brojeva $a$ i $b$. Primjenom Euklidovog algoritma dobivamo da je $$M(n+1,2n-1)=M(n+1,2n-1-2(n+1))=M(n+1,-3)=M(n+1,3)$$ Dakle ako je $n+1$ djeljivo s $3$, onda je $3$ ciklusa, inače je samo $1$. Ako je samo $1$ ciklus očito je $k = n$. Ako je pak $3$ ciklusa koji svaki sadrži $\dfrac{2n-1}{3}$ vrha, svaki ciklus može imati maksimalno $\Big{\lfloor}\dfrac{2n-1}{6}\Big{\rfloor}$ crvenih točaka u lošem bojanju. Dakle, u ovom slučaju $k = 3\Big{\lfloor}\dfrac{2n-1}{6}\Big{\rfloor} +1$