IMO 2007

Key idea: a sorted list can’t follow a big early value and a small late value at the same time, so it misses one of them by at least $\tfrac d2$. The running maximum shifted down by $\tfrac d2$ misses nothing by more.

(a) Choose $i$ with $d_i=d$. There are indices $p\le i$ with $a_p=\max_{j\le i}a_j$ and $r\ge i$ with $a_r=\min_{j\ge i}a_j$, so $p\le r$ and $a_p-a_r=d$. Since the $x$’s are sorted, $x_p\le x_r$. Then $$(a_p-x_p)+(x_r-a_r)\ \ge\ a_p-a_r=d,$$ so one of $|x_p-a_p|$ and $|x_r-a_r|$ is at least $\tfrac d2$.

(b) Let $M_i=\max(a_1,\dots,a_i)$ and $x_i=M_i-\tfrac d2$. This list is sorted because $M_i$ never decreases. For every $i$:

• $x_i-a_i=M_i-a_i-\tfrac d2\ge-\tfrac d2$, since $M_i\ge a_i$;
• $x_i-a_i\le M_i-\min_{j\ge i}a_j-\tfrac d2=d_i-\tfrac d2\le\tfrac d2$, since $a_i\ge\min_{j\ge i}a_j$.

So $\max|x_i-a_i|\le\tfrac d2$, and by part (a) it equals $\tfrac d2$.

Key idea: reduce to $CF=CG$. The cyclic quadrilateral makes two right triangles similar, and that gives a second formula for the ratio of the distances from $E$ to the lines $DC$ and $BC$. The two formulas agree only when $CF=CG$.

Reduction. Since $AB\parallel FC$, $\angle CFG=\angle BAG$, and since $AD\parallel CG$, $\angle CGF=\angle DAG$. So the line bisects angle $DAB$ exactly when $\angle CFG=\angle CGF$, that is, when $CF=CG$.

Setup. $F$ is inside segment $DC$, so $G$ is on line $BC$ beyond $C$. $E$ is the circumcenter of triangle $CFG$; let $\rho$ be its circumradius. Let $M$ and $N$ be the midpoints of $CF$ and $CG$, so $EM\perp DC$ and $EN\perp BC$, and $$EM=\sqrt{\rho^2-\tfrac14CF^2},\qquad EN=\sqrt{\rho^2-\tfrac14CG^2}.$$

Similar right triangles. $M$ lies on segment $DC$ and $N$ on ray $BC$, so $\angle EDM=\angle EDC$ and $\angle EBN=\angle EBC$. These are inscribed angles of circle $BCED$ on the chord $EC$, so they are equal or supplementary. Both are acute angles of right triangles, so they are equal. Hence triangles $EMD$ and $ENB$ are similar, and $$\frac{EM}{EN}=\frac{DM}{BN}.$$

The ratio $DM/BN$. Triangles $FDA$ and $FCG$ are similar (parallel sides), so $DF=AD\cdot\dfrac{CF}{CG}=BC\cdot\dfrac{CF}{CG}$. Then $$DM=DF+\tfrac12CF=\frac{CF}{CG}\Big(BC+\tfrac12CG\Big)=\frac{CF}{CG}\cdot BN .$$ So $\dfrac{EM}{EN}=\dfrac{CF}{CG}$.

Finish. Squaring, $CG^2\big(\rho^2-\tfrac14CF^2\big)=CF^2\big(\rho^2-\tfrac14CG^2\big)$, so $\rho^2CG^2=\rho^2CF^2$ and $CF=CG$. By the reduction, the line is the bisector of angle $DAB$.

Key idea: first shift members of a largest clique until the two rooms are within $1$ of each other. If the second room is still ahead by one, move outsiders back one at a time, choosing them so that they are friends with all the clique members left behind. A clique that grew too big in the first room would then extend to a clique larger than the largest one.

For a group $X$ write $\omega(X)$ for the size of its largest clique. Moving one person from one room to the other changes each room’s $\omega$ by at most $1$. If there is at least one competitor, the largest clique size is at least $1$, and being even it is $2m$ with $m\ge1$. Fix a clique $K$ with $|K|=2m$.

Phase 1. Put $K$ in room $A$ and everybody else in room $B$. While $\omega(A)>\omega(B)$, move one member of $K$ from $A$ to $B$. Room $A$ always consists of members of $K$, so $\omega(A)=|A|$. Once $|A|=m$, room $B$ holds $m$ members of $K$, so $\omega(B)\ge m=|A|$. So the process stops with $|A|=a\ge m$.

If no one was moved, then $\omega(B)\ge2m$, and since no clique is larger, $\omega(B)=2m=\omega(A)$: done. Otherwise, just before the last move we had $a+1>\omega(B_{\text{before}})$, and the move added at most $1$, so $a\le\omega(B)\le a+1$. If $\omega(B)=a$ we are done. So assume $\omega(A)=a$ and $\omega(B)=a+1$.

Let $S=B\cap K$, the clique members in room $B$. Then $|S|=2m-a\le m\le a$.

Phase 2. Repeat the following.

• (i) If some clique $C\subseteq B$ of size $a+1$ misses a member $s$ of $S$, move $s$ to $A$. Room $A$ now contains the clique $(A\cap K)\cup\{s\}$ of size $a+1$, and $\omega(A)$ grew by at most $1$, so $\omega(A)=a+1$. Room $B$ still contains $C$, so $\omega(B)=a+1$. Done.
• (ii) Otherwise every clique of size $a+1$ in $B$ contains all of $S$. Take one, $C$. Since $|C|=a+1>|S|$, it has a member $x\notin K$, and $x$ is friends with everyone in $S$. Move $x$ to $A$.

Room $A$ never gets a clique of size $a+1$ in step (ii). Room $A$ consists of the $a$ members of $A\cap K$ plus people moved in step (ii), and each of those is friends with all of $S$. (The set $S$ does not change during Phase 2.) Suppose $Q\subseteq A$ were a clique of size $a+1$. Its members from $K$ are friends with $S$ because $K$ is a clique, and its other members are friends with $S$ by the choice in (ii). So $Q\cup S$ is a clique of size $$(a+1)+(2m-a)=2m+1,$$ larger than the largest clique. Impossible. So after each step (ii), $\omega(A)=a$ (it can’t drop, since $A\cap K$ stays), and $\omega(B)$ is $a$ or $a+1$. If it is $a$, we are done; otherwise repeat.

The process ends. Each step (ii) removes from $B$ someone outside $K$. If $B$ ever held only $S$, we would have $\omega(B)=|S|\le a$. So after finitely many steps one of the stopping cases happens, and the two rooms have equal largest cliques.

Key idea: the circumcenter is equally far from $P$ and $Q$, so $P$ and $Q$ sit symmetrically on the chord $CR$. Then both areas reduce to the same product.

Let $a=BC$, $b=CA$, $\gamma=\angle C$, and $O$ the circumcenter, where the perpendicular bisectors meet. So $OP\perp BC$ and $OQ\perp CA$.

Symmetric points. The bisector $CR$ makes the angle $\tfrac\gamma2$ with both $CB$ and $CA$. So the line $OP$ (perpendicular to $CB$) and the line $OQ$ (perpendicular to $CA$) both make the angle $90^\circ-\tfrac\gamma2$ with $CR$. So triangle $OPQ$ is isosceles with $OP=OQ$, and the foot $H$ of the perpendicular from $O$ to $CR$ is the midpoint of $PQ$. $H$ is also the midpoint of the chord $CR$. Hence $$CQ=PR,\qquad CP=QR .$$

Lengths. In the right triangle $CKP$, $CK=\tfrac a2$ and the angle at $C$ is $\tfrac\gamma2$, so $CP=\dfrac{a}{2\cos(\gamma/2)}$. In the same way $CQ=\dfrac{b}{2\cos(\gamma/2)}$.

Areas. Use $RP$ and $RQ$ (on line $CR$) as bases. The distance from $K$ to line $CR$ is $CK\sin\tfrac\gamma2=\tfrac a2\sin\tfrac\gamma2$, and from $L$ it is $\tfrac b2\sin\tfrac\gamma2$. So $$[RPK]=\tfrac12\,RP\cdot\tfrac a2\sin\tfrac\gamma2=\tfrac12\,CQ\cdot\tfrac a2\sin\tfrac\gamma2=\frac{ab\sin\frac\gamma2}{8\cos\frac\gamma2},$$ $$[RQL]=\tfrac12\,RQ\cdot\tfrac b2\sin\tfrac\gamma2=\tfrac12\,CP\cdot\tfrac b2\sin\tfrac\gamma2=\frac{ab\sin\frac\gamma2}{8\cos\frac\gamma2}.$$ The two areas are equal.

Key idea: the condition is the same as $4ab-1\mid(a-b)^2$. If $a\ne b$, the quotient equation is a quadratic in $a$, and jumping to its other root gives a smaller solution.

Reduce. Let $q=4ab-1$. Mod $q$ we have $4ab\equiv1$, so $$(4a^2-1)\cdot4b=4a\cdot4ab-4b\equiv4a-4b\pmod q .$$ Squaring, $16b^2(4a^2-1)^2\equiv16(a-b)^2$. Since $q$ is odd and coprime to $b$, $\gcd(16b^2,q)=1$. So $q\mid(4a^2-1)^2$ exactly when $q\mid(a-b)^2$.

Descent. Suppose $a\ne b$. Then $(a-b)^2=kq$ with $k\ge1$, for a fixed $k$. The equation $(x-y)^2=k(4xy-1)$ is symmetric. Among its positive solutions with $x\ne y$, pick one $(a,b)$ with $a>b$ and $a+b$ smallest. As a quadratic in $a$, $$a^2-(2+4k)b\,a+(b^2+k)=0 .$$ The other root is $a'=(2+4k)b-a=\dfrac{b^2+k}{a}$, a positive integer, and $(a',b)$ is again a solution. $a'\ne b$, since $a'=b$ would give $k=0$.

Now $k=\dfrac{(a-b)^2}{4ab-1}\le(a-b)^2<(a-b)(a+b)=a^2-b^2$, so $b^2+k<a^2$ and $a'<a$. Then $(a',b)$ (or $(b,a')$, whichever has the larger entry first) is a solution with $x\ne y$ and a smaller sum. That contradicts the choice of $(a,b)$.

So $a=b$.

Key idea: the product of the planes’ equations is a polynomial that vanishes on the grid except at the origin. A triple finite difference shows such a polynomial has degree at least $3n$.

Enough. The $3n$ planes $x+y+z=t$, $t=1,\dots,3n$, cover every grid point except the origin, and miss the origin.

One-variable fact. For a polynomial $g$ of degree less than $n$, $\sum_{i=0}^n(-1)^i\binom ni g(i)=0$. (This is the $n$-th finite difference of $g$; each difference lowers the degree by one. It is enough to check it for $g(i)=i^e$ with $e<n$.)

Three variables. Let $P(x,y,z)$ have degree less than $3n$. Every monomial $x^\alpha y^\beta z^\gamma$ of $P$ has $\alpha+\beta+\gamma<3n$, so one exponent is less than $n$. Then $$\sum_{i,j,k=0}^n(-1)^{i+j+k}\binom ni\binom nj\binom nk\,i^\alpha j^\beta k^\gamma$$ splits into a product of three one-variable sums, one of which is $0$. By linearity, $$\sum_{i,j,k}(-1)^{i+j+k}\binom ni\binom nj\binom nk P(i,j,k)=0\quad\text{whenever }\deg P<3n .$$

Lower bound. Suppose $N$ planes cover the set and miss the origin. Write the $m$-th plane as $\ell_m(x,y,z)=d_m$ with $d_m\ne0$, and let $P=\prod_m(\ell_m-d_m)$, of degree $N$. It vanishes at every grid point except the origin, where it is $\prod(-d_m)\ne0$. So the alternating sum above equals $P(0,0,0)\ne0$. Hence $\deg P\ge3n$, that is, $N\ge3n$.