International Mathematical Olympiad

Proof We provide an algorithm to distribute the competitors. Denote the rooms $A$ and $B$. 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 $A$ and $B$ be the sets of competitors in room $A$ and $B$. Let $C(A)$ and $C(B)$ be the largest size of clique in room $A$ and $B$ respectively.

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

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

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

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

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