Maths Olympiad Prep

Library / /122 of 196

Combinatorics Difficulty 5.4 AIME, harder Prove it Soviet Union

Problem:

In a group of people every person has less than 44 enemies. Assume that AA is BB's enemy iff BB is AA's enemy. Show that we can divide the group into two parts, so that each person has at most one enemy in his part.

Solution

Solution:

We model the group as a graph where each person is a vertex and an edge connects two people if they are enemies. Each vertex has degree less than 44.

We need to partition the vertices into two sets so that each vertex has at most one neighbor (enemy) in its own set.

We proceed by induction on the number of people.

Base case: For 11 or 22 people, the statement is clear.

Inductive step: Suppose the statement is true for all groups with fewer than nn people. Consider a group with nn people.

Since every person has less than 44 enemies, the graph has maximum degree at most 33.

Pick any person vv. Remove vv from the group. By the induction hypothesis, the remaining group can be partitioned into two sets AA and BB so that each person has at most one enemy in their own set.

Now, add vv back. vv has at most 33 enemies, say xx, yy, zz (possibly fewer). These enemies are in AA and BB in some way.

If at most one of xx, yy, zz is in AA, put vv in AA; then vv has at most one enemy in AA (his own set).

If at least two of xx, yy, zz are in AA, then at most one is in BB, so put vv in BB.

Thus, we can always place vv in a set so that he has at most one enemy in his own set.

This completes the induction.

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.