IMO 2006 Shortlisted Problems

We use capital letters to denote unit squares; $O$ is the top left corner square. For any two squares $X$ and $Y$ let $[XY]$ be the smallest grid rectangle containing these two squares. Strawberries lie on some squares in arrangement $\mathcal{A}$. Put a plum on each square of the target configuration $\mathcal{B}$. For a square $X$ denote by $a(X)$ and $b(X)$ respectively the number of strawberries and the number of plums in $[OX]$. By hypothesis $a(X)\le b(X)$ for each $X$, with strict inequality for some $X$ (otherwise the two arrangements coincide and there is nothing to prove). The idea is to show that by a legitimate switch one can obtain an arrangement ${\mathcal{A}}^{\prime }$ such that $$\begin{array}{c}a(X)\le a^{\prime }(X)\le b(X)\text{ for each }X;\sum _{X}a(X)<\sum _X{a}^{\prime }(X)\end{array}\text{\hspace{1em}(1)}$$ (with $a^{\prime }(X)$ defined analogously to $a(X)$; the sums range over all unit squares $X$ ). This will be enough because the same reasoning then applies to ${\mathcal{A}}^{\prime }$, giving rise to a new arrangement ${\mathcal{A}}^{\prime \prime }$, and so on (induction). Since $\sum a(X)<\sum a^{\prime }(X)<\sum a^{\prime \prime }(X)<\dots$ and all these sums do not exceed $\sum b(X)$, we eventually obtain a sum with all summands equal to the respective $b(X)$s; all strawberries will meet with plums. Consider the uppermost row in which the plum and the strawberry lie on different squares $P$ and $S$ (respectively); clearly $P$ must be situated left to $S$. In the column passing through $P$, let $T$ be the top square and $B$ the bottom square. The strawberry in that column lies below the plum (because there is no plum in that column above $P$, and the positions of strawberries and plums coincide everywhere above the row of $P$ ). Hence there is at least one strawberry in the region $[BS]$ below $[PS]$. Let $V$ be the position of the uppermost strawberry in that region.

$O$		$T$					I
							I
		$P$			$U$		1			$S$
							1	1
							1
-	-	-	-	-	-	- -	${\underline{X}}^{\prime }$
									$R$
					$V$					$W$
		$B$

Denote by $W$ the square at the intersection of the row through $V$ with the column through $S$ and let $R$ be the square vertex-adjacent to $W$ up-left. We claim that $$\begin{array}{c}a(X)<b(X)\text{ for all }X\in [PR].\end{array}\text{\hspace{1em}(2)}$$ This is so because if $X\in [PR]$ then the portion of $[OX]$ left to column $[TB]$ contains at least as many plums as strawberries (the hypothesis of the problem); in the portion above the row through $P$ and $S$ we have perfect balance; and in the remaining portion, i.e. rectangle $[PX]$ we have a plum on square $P$ and no strawberry at all. Now we are able to perform the required switch. Let $U$ be the square at the intersection of the row through $P$ with the column through $V$ (some of $P,U,R$ can coincide). We move strawberries from squares $S$ and $V$ to squares $U$ and $W$. Then $$a^{\prime }(X)=a(X)+1\text{ for }X\in [UR];a^{\prime }(X)=a(X)\text{ for other }X.$$ And since the rectangle $[UR]$ is contained in $[PR]$, we still have $a^{\prime }(X)\le b(X)$ for all $S$, in view of (2); conditions (1) are satisfied and the proof is complete.