MathDB

4

Part of 2003 IMAR Test

Problems(1)

any 2 on an island are friends or enemies, min no of necklaces

Source: IMAR Test 2003 p4

4/18/2020
On an island live nn (n≥2n \ge 2) xyzxyzs. Any two xyzxyzs are either friends or enemies. Every xyzxyz wears a necklace made of colored beads such that any two xyzxyzs that are befriended have at least one bead of the same color and any two xyzxyzs that are enemies do not have any common colors in their necklaces. It is also possible for some necklaces not to have any beads. What is the minimum number of colors of beads that is sufficient to manufacture such necklaces regardless on the relationship between the xyzxyzs?
combinatorics