BY-MO 2001 Problem 10
There are aborigines on an island. Any two of them are either friends or enemies. One day, the chieftain orders that all citizens (including himself) make and wear a necklace with zero or more stones so that: (i) given a pair of friends, there exists a color such that each has a stone of that color; (ii) given a pair of enemies,there does not exist a color such that each a stone of that color.
(a) Prove that the aborigines can carry out the chieftain's order. (b) What is the minimum number of colors of stones required for the aborigines to carry out the chieftain's order?
Dataset text AI-MO AoPS. Quoted with source.
Solutions
No solution is on olymmath yet. Official and human solutions come first when they arrive. AI solutions come after them, with a label.
Similar problems
These problems have the most words in common with this statement.