Maths Olympiad Prep

Library / /20 of 28

Combinatorics Difficulty 8.1 Shortlist Prove it Hong Kong

In a committee there are nn members. Each pair of members are either friends or enemies. Each committee member has exactly three enemies. It is also known that for each committee member, an enemy of his friend is automatically his own enemy. Find all possible value(s) of nn.

Solution

Suppose AA and BB are enemies. By the given condition, every other member cannot be a friend of both AA and BB. Since each of AA and BB has 2 more enemies other than themselves, we must have n2+2×2=6n \le 2 + 2 \times 2 = 6. Also, as each member has 3 enemies, we have n4n \ge 4, and there are 3n2\frac{3n}{2} pairs of enemies. This shows nn is even, and hence nn can only be 4 or 6.
To give examples for n=4n = 4 and n=6n = 6, we use terminologies in graph theory. Suppose vertices denote the members and edges join pairs of enemies. Then K4K_4 and K3,3K_{3,3} are examples for n=4n = 4 and n=6n = 6 respectively.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.