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. (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 largest size of a 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.

Official text of the problem. Official problem paper (PDF)

Solution

Let \(V\) be the set of competitors. For \(S\subseteq V\), write \(\omega(S)\) for the largest clique size in \(S\), with \(\omega(\varnothing)=0\).

If \(V=\varnothing\), both rooms may be empty. Otherwise, suppose for a contradiction that no required arrangement exists. Define \[ f(S)= \begin{cases} 1,&\omega(S)>\omega(V\setminus S),\\ 0,&\omega(S)<\omega(V\setminus S). \end{cases} \] Our assumption ensures that \(f\) is defined for every subset. It is monotone: if \(S\subseteq T\), then \(f(S)\le f(T)\). Moreover, \[ f(V\setminus S)=1-f(S). \] For brevity, write \(S+x=S\cup\{x\}\).

We first prove that whenever \(x,y\) are not friends and \(S\) contains neither, \[ f(S)+f(S+x+y)=f(S+x)+f(S+y). \tag{1} \] Put \(T=V\setminus(S+x+y)\). Suppose \(f(S+x)=f(S+y)=0\). Adding one competitor increases a largest clique size by at most one, so \[ \omega(S+x)<\omega(T+y)\le \omega(T)+1, \] and hence \(\omega(S+x)\le\omega(T)\). Similarly, \(\omega(S+y)\le\omega(T)\). Since no clique contains both \(x\) and \(y\), \[ \omega(S+x+y)=\max\{\omega(S+x),\omega(S+y)\}\le\omega(T). \] Thus \(f(S+x+y)=0\). Interchanging the rooms also shows that if \(f(S+x)=f(S+y)=1\), then \(f(S)=1\). Together with monotonicity, these implications give (1).

Now fix a largest clique \(C\), of even size \(m>0\). We claim that, for subsets of \(C\), \(f(S)\) depends only on \(|S|\). Indeed, let \(S,S'\subseteq C\) have size \(r\) and differ by replacing one member. Both have clique number \(r\). If their \(f\)-values differed, the clique numbers of their complements would be respectively at most \(r-1\) and at least \(r+1\). This is impossible: replacing one competitor changes a largest clique size by at most one. Any two \(r\)-element subsets can be connected by such replacements, proving the claim.

Since \(f(\varnothing)=0\), \(f(C)=1\), and \(f\) is monotone, there is an integer \(t\), with \(1\le t\le m\), such that \[ f(S)=1\quad\Longleftrightarrow\quad |S|\ge t \qquad(S\subseteq C). \tag{2} \]

We next prove, by induction on \(|U|\), that \[ f(U\cup S)=f(S) \qquad\text{for every }U\subseteq V\setminus C,\ S\subseteq C. \tag{3} \] The case \(U=\varnothing\) is immediate. Assume (3) holds for \(U\), and take \(v\notin U\cup C\). Because \(C\) is a largest clique, some \(x\in C\) is not friends with \(v\).

For \(S\subseteq C\), put \[ d(S)=f(U\cup S+v)-f(U\cup S). \] Monotonicity gives \(d(S)\in\{0,1\}\), while (1) gives \[ d(S)=d(S+x)\qquad(x\notin S). \tag{4} \]

Suppose \(d(S)=1\) for some \(S\). By (4), we may remove \(x\) from \(S\) if necessary. Thus assume \(x\notin S\). The induction hypothesis and (2) imply \(|S|\le t-1\). Extend \(S\) to a set \[ S\subseteq T\subseteq C\setminus\{x\}, \qquad |T|=t-1. \] Then \(f(U\cup T)=0\), while monotonicity gives \(f(U\cup T+v)=1\). Hence \(d(T)=1\). But \(|T+x|=t\), so \(f(U\cup T+x)=1\), giving \(d(T+x)=0\), contrary to (4). Therefore every \(d(S)\) is zero, completing the induction.

Finally, choose \(S\subseteq C\) with \(|S|=m/2\), and put \(U=V\setminus C\). Since \(S\) and \(C\setminus S\) have equal sizes, their \(f\)-values agree. But (3) and complementation give \[ f(S)=f(U\cup S)=1-f(C\setminus S)=1-f(S), \] impossible for a value in \(\{0,1\}\).

The assumed impossibility is therefore false, and the required arrangement exists. \(\square\)

The solution was checked against the official IMO shortlist solutions.