Na otoku živi
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
domorodaca. Svaka dva su ili prijatelji ili neprijatelji. Jednog dana poglavica naredi svim stanovnicima (uključujući i sebe) da si naprave i da nose kamene ogrlice, tako da svaka dva prijatelja imaju barem po jedan istovrsni kamen u svojim ogrlicama, a da se sva kamenja u ogrlicama dvaju neprijatelja razlikuju. (Ogrlica može biti i bez kamenja) Dokažite da se poglavičina zapovijed može izvršiti koristeći
![\left\lfloor \frac{n^2}{4} \right\rfloor](/media/m/4/f/6/4f62fb471f4a7bdca77e1d83f3aef29a.png)
različitih vrsta kamenja, i da se općenito ovo ne može postići s manje kamenja.
%V0
Na otoku živi $n$ domorodaca. Svaka dva su ili prijatelji ili neprijatelji. Jednog dana poglavica naredi svim stanovnicima (uključujući i sebe) da si naprave i da nose kamene ogrlice, tako da svaka dva prijatelja imaju barem po jedan istovrsni kamen u svojim ogrlicama, a da se sva kamenja u ogrlicama dvaju neprijatelja razlikuju. (Ogrlica može biti i bez kamenja) Dokažite da se poglavičina zapovijed može izvršiti koristeći $\left\lfloor \frac{n^2}{4} \right\rfloor$ različitih vrsta kamenja, i da se općenito ovo ne može postići s manje kamenja.