Olympiad Combinatorics

Example 12 [IMO 2007, Problem 3] 
In a mathematical competition some competitors are friends; 
friendship is always mutual. Call a group of competitors a clique if 
each two of them are friends. The number of members in a clique 
is called its size. It is known that the size of the largest clique(s) is 
even. Prove that the competitors can be arranged in two rooms 
such that the size of the largest cliques in one room is the same as 
the size of the largest cliques in the other room.
Answer:
Let M be one of the cliques of largest size, |M| = 2m. First send all 
members of M to Room A and all other people to Room B. Let c(A) 

---

Chapter 1: Algorithms 
21 
and c(B) denote the sizes of the largest cliques in rooms A and B at 
a given point in time. Since M is a clique of the largest size, we 
initially have c(A) =|M|≥ c(B). Now we want to “balance things 
out”. As long as c(A) > c(B), send one person from Room A to 
Room B. In each step, c(A) decreases by one and c(B) increases by 
at most one. So at the end we have c(A)≤ c(B) ≤ c(A) + 1. We also 
have c(A) = |A| ≥ m at the end. Otherwise we would have at least 
m+1 members of M in Room B and at most m−1 in Room A, 
implying c(B)−c(A) ≥ (m+1)−(m−1) = 2.
Clearly if c(A) = c(B) we are done so at this stage the only case 
we need to consider is c(B) - c(A) = 1. Let c(A) = k, c(B) = k+1. Now 
if there is a competitor in B, who is also in M but is not in the 
biggest clique in B, then by sending her to A, c(B) doesn’t change 
but c(A) increases by 1 and we are done. Now suppose there is no 
such competitor. We do the following: take each clique of size k+1 
in B and send one competitor to A. At the end of this process, c(B) 
= k. Now we leave it to the reader to finish the proof by showing 
that c(A) is still k. (You will need to use the supposition that there 
is no competitor in B who is also in M but not in the biggest clique 
of B. This means that every clique in B of size (k+1) contains 
B∩M). ■