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

Source: IMAR Test 2003 p4

April 18, 2020
combinatorics

Problem Statement

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?
Back to ProblemsView on AoPS