Problem: In a mathematical competition some competitors are (mutual) friends.
Call a group of competitors a \emph{clique} if each two of them are friends.
Given that the largest size of a clique is even,
prove that the competitors can be arranged into 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: Take the obvious graph interpretation $G$.
We paint red any vertices in one of the maximal cliques $K$,
which we assume has $2r$ vertices, and paint the remaining vertices green.
We let $\alpha(\bullet)$ denote the clique number.

Initially, let the two rooms $A = K$, $B = G-K$.
\begin{claim*}
  We can move at most $r$ vertices of $A$ into $B$
  to arrive at $\alpha(A) \le \alpha(B) \le \alpha(A)+1$.
\end{claim*}
\begin{proof}
  This is actually obvious by discrete continuity.
  We move one vertex at a time, noting $\alpha(A)$ decreases by one at each step,
  while $\alpha(B)$ increases by either zero or one at each step.

  We stop once $\alpha(B) \ge \alpha(A)$, which happens before we have moved $r$ vertices
  (since then we have $\alpha(B) \ge r = \alpha(A)$).
  The conclusion follows.
\end{proof}

So let's consider the situation
\[ \alpha(A) = k \ge r \qquad\text{and}\qquad \alpha(B) = k+1. \]

At this point $A$ is a set of $k$ red vertices,
while $B$ has the remaining $2r-k$ red vertices (and all the green ones).
An example is shown below with $k=4$ and $2r = 6$.

\begin{center}
\begin{asy}
size(10cm);
pair K1 = 2*dir(45);
pair K2 = 2*dir(135);
pair K3 = 2*dir(225);
pair K4 = 2*dir(315);

label("$A$", (0,2), dir(90), red);
label("$\alpha(A) = k$", (0,-2.5), dir(90), red);
label("$k$ red vertices", (0,-2.5), dir(-90), red);

pair K5 = (6,1);
pair K6 = (6,-1);

draw(K1--K5, palered);
draw(K2--K5, palered);
draw(K3--K5, palered);
draw(K4--K5, palered);

draw(K1--K6, palered);
draw(K2--K6, palered);
draw(K3--K6, palered);
draw(K4--K6, palered);

pair B1 = (4.8,1.3);
pair B2 = (3.7,0);
pair B3 = (4.8,-1.3);

pair C1 = (7.2,1.3);
pair C2 = (8.3,0);
pair C3 = (7.2,-1.3);

draw(K5--B1--K6, paleblue);
draw(K5--B2--K6, paleblue);
draw(K5--B3--K6, paleblue);
draw(B1--B2--B3--cycle, paleblue);
draw(K5--C1--K6, paleblue);
draw(K5--C2--K6, paleblue);
draw(K5--C3--K6, paleblue);
draw(C1--C2--C3--cycle, paleblue);

draw(K1--K2--K3--K4--cycle, red+1);
draw(K1--K3, red+1);
draw(K2--K4, red+1);
draw(K5--K6, red+1);

dot(K1, red);
dot(K2, red);
dot(K3, red);
dot(K4, red);
dot(K5, red);
dot(K6, red);
dot(B1, deepgreen);
dot(B2, deepgreen);
dot(B3, blue);
dot(C1, deepgreen);
dot(C2, deepgreen);
dot(C3, blue);
draw(circle(B3, 0.15), blue);
draw(circle(C3, 0.15), blue);

label("$B$", (6,2), dir(90), deepgreen);
label("$\alpha(B) = k+1$", (6,-2.5), dir(90), deepgreen);
label("$2r-k$ red vertices", (6,-2.5), dir(-90), deepgreen);

draw((3,2.8)--(3,-2.8), black+1.5);
\end{asy}
\end{center}

Now, if we can move any red vertex from $B$ back to $A$
without changing the clique number of $B$, we do so, and win.

Otherwise, it must be the case that \emph{every}
$(k+1)$-clique in $B$ uses \emph{every} red vertex in $B$.
For each $(k+1)$-clique in $B$ (in arbitrary order), we do the following procedure.
\begin{itemize}
  \ii If all $k+1$ vertices are still green, pick one and re-color it blue.
  This is possible since $k+1 > 2r-k$.
  \ii Otherwise, do nothing.
\end{itemize}
Then we move all the blue vertices from $B$ to $A$,
one at a time, in the same order we re-colored them.
This forcibly decreases the clique number of $B$ to $k$,
since the clique number is $k+1$ just before the last blue vertex is moved,
and strictly less than $k+1$ (hence equal to $k$) immediately after that.

\begin{claim*}
  After this, $\alpha(A) = k$ still holds.
\end{claim*}
\begin{proof}
  Assume not, and we have a $(k+1)$-clique
  which uses $b$ blue vertices and $(k+1)-b$ red vertices in $A$.
  Together with the $2r-k$ red vertices already in $B$ we then get a clique of size
  \[ b + \left( (k+1-b) \right) + \left( 2r-k \right) = 2r + 1 \]
  which is a contradiction.
\end{proof}

\begin{remark*}
  Dragomir Grozev posted the following motivation on \href{https://dgrozev.wordpress.com/2019/12/05/splitting-the-cliques-of-a-graph-imo-2007-p3/}{his blog}:
  \begin{quote}
  I think, it's a natural idea to place all students in one room and begin
  moving them one by one into the other one.
  Then the max size of the cliques in the first and second room
  increase (resp.\ decrease) at most with one.
  So, there would be a moment both sizes are almost the same.
  At that moment we may adjust something.

  Trying the idea, I had some difficulties
  keeping track of the maximal cliques in the both rooms.
  It seemed easier all the students in one of the rooms to comprise a clique.
  It could be achieved by moving only the members of the maximal clique.
  Following this path the remaining obstacles can be overcome naturally.
  \end{quote}
\end{remark*}