Maths Olympiad Prep

Library / /88 of 106

Combinatorics Difficulty 8.8 Shortlist Prove it China

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. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.
Given that, in this competition, the size of the largest clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Solution

Proof We provide an algorithm to distribute the competitors.
Denote the rooms AA and BB. At some initial stage, we move one person at a time from one room to the other one. We achieve the target by going through several adjustments. In every step of the algorithm, let AA and BB be the sets of competitors in room AA and BB. Let C(A)C(A) and C(B)C(B) be the largest size of clique in room AA and BB respectively.

Step 1: Let MM be the largest clique of all competitors, M=2m|M| = 2m.
Move all members of MM to room AA, and the remained ones to room BB.
Since MM is the largest clique of all competitors, we have C(A)=MC(B)C(A) = |M| \ge C(B).

Step 2: If C(A)>C(B)C(A) > C(B), move one person from room AA to room BB. (In view of C(A)>C(B)C(A) > C(B), we have AA \ne \emptyset.)
After every operation is done, C(A)C(A) decreases by 11 while C(B)C(B) increases by 11 at most. These operations will not end until
C(A)C(B)C(A)+1. C(A) \le C(B) \le C(A) + 1.
At that time, we also have C(A)=AmC(A) = |A| \ge m. (Otherwise there are at least m+1m+1 members of MM in room BB, at most m1m-1 members in room AA, then C(B)C(A)(m+1)(m1)=2C(B) - C(A) \ge (m+1) - (m-1) = 2, it is impossible.)

Step 3: Denote K=C(A)K = C(A). If C(B)=KC(B) = K, we are done; or else C(B)=K+1C(B) = K + 1. From the above discussion,
K=A=AMm,BMm. K = |A| = |A \cap M| \ge m, \quad |B \cap M| \le m.

Step 4: If there is a clique CC in room BB with C=K+1|C| = K + 1 and a competitor xBMx \in B \cap M but xCx \notin C, then move xx to room AA, we are done.
In fact, after the operation, there are K+1K+1 members of MM in room AA, so C(A)=K+1C(A) = K+1. Since xCx \notin C, whose removal does not reduce CC, C(B)=CC(B) = C. Therefore, C(A)=C(B)=K+1C(A) = C(B) = K+1.
If such competitor xx does not exist, then each largest clique in room BB contains BMB \cap M as a subset. In this case, we do step 5.

Step 5: Choose any of the largest clique CC (C=K+1|C| = K+1) in room BB, move a member of CMC \setminus M to room AA. (In view of C=K+1>mBM|C| = K+1 > m \ge |B \cap M|, we know CMC \setminus M \ne \emptyset.)
Since we only move one person at a time from room BB to room AA, so C(B)C(B) decreases by 11 at most. At the end of this step, we have C(B)=KC(B) = K.
Now, there is a clique AMA \cap M in AA, AM=K|A \cap M| = K. So C(A)KC(A) \ge K.
We prove C(A)=KC(A) = K as follows.
Let QQ be any clique of room AA. We only need to show QK|Q| \le K.
In fact, the members of room AA can be classified into two:
(1) Some members of MM in view of MM being a clique, are friends with all the members of BMB \cap M.
(2) The members move from room BB to room AA at step 5, they are friends of BMB \cap M.
So, every member of QQ and members of BMB \cap M are friends. What is more, QQ and BMB \cap M both are cliques, so is Q(BM)Q \cup (B \cap M).
Since MM is the largest clique of all competitors,
MQ(BM)=Q+BM |M| \ge |Q \cup (B \cap M)| = |Q| + |B \cap M|
=Q+MAM. = |Q| + |M| - |A \cap M|.
So QAM=K|Q| \le |A \cap M| = K. Therefore, after these 5 steps, we have C(A)=C(B)=KC(A) = C(B) = K.

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 and solution reproduced as published; topic and difficulty added by this site.