NO-ABEL 2004 Problem 4

Among the $n$ inhabitants of an island, where $n$ is even, every two are either friends or enemies. Some day, the chief of the island orders that each inhabitant (including himself) makes and wears a necklace consisting of marbles, in such a way that two necklaces have a marble of the same type if and only if their owners are friends. (a) Show that the chief's order can be achieved by using $n^2/4$ different types of stones. (b) Prove that this is not necessarily true with less than $n^2/4$ types.