NMO Selection Tests for the Balkan and International Mathematical Olympiads

Transform $K$ by a suitable two-step Steiner-Edler symmetrization. First, perform a horizontal translation of each slice $K\cap (\mathbb{R}\times y)$ to place it symmetrically about the vertical line $x=\frac{1}{2}$. It is readily checked that the image $K^{\prime }$ of $K$ under this transformation is a closed convex subset of the open square $(1/2-n/2,1/2+n/2)\times (0,n)$, symmetrical about the vertical line $x=1/2$, and $\text{area }{K}^{\prime }=\text{area }K\ge n$. (Also, the transformation does not increase perimeters, a fact which will not be used in the sequel.) In addition, if $K$ contains no lattice point, so does $K^{\prime }$. Indeed, if $K^{\prime }$ contained one such, say $i\times j$, then the line $y=j$ would intersect $K^{\prime }$ in a closed line segment of length at least $1$, so it would also intersect $K$ in a closed line segment of the same length; the latter, in turn, would contain at least one lattice point – a contradiction.

Next, apply the pattern vertically to further symmetrize $K^{\prime }$ about the horizontal line $y=1/2$. The resulting image $K^{\prime \prime }$ is a closed convex subset of the open square $(1/2-n/2,1/2+n/2)\times (1/2-n/2,1/2+n/2)$, symmetrical about both lines $x=1/2$ and $y=1/2$ – whence centrally symmetric about the point $1/2\times 1/2$ – and of course $\text{area }{K}^{\prime \prime }=\text{area }{K}^{\prime }=\text{area }K\ge n$. Then if $K$ contains no lattice point, so does $K^{\prime \prime }$.

Now let $a=\sup \{x:x\times 1/2\in K^{\prime \prime }\}$ and $b=\sup \{y:1/2\times y\in K^{\prime \prime }\}$ and notice that $a-1/2<n/2$ and $b-1/2<n/2$ – both inequalities are strict, for $K^{\prime \prime }$ is closed. Let further $K_0=K^{\prime \prime }\cap \{x\times y:x\ge 1/2\text{ and }y\ge 1/2\}$ be the upper right quarter of $K^{\prime \prime }$. Clearly, $K_0$ is a closed convex set, and $\text{area }{K}_0=(\text{area }{K}^{\prime \prime })/4\ge n/4$. Suppose, if possible, that $K$ contains no lattice point. Then so does $K_0$, so by convexity it must lie below some line through the lattice point $1\times 1$ with a non-positive slope; that is, $$K_0\subset H=\{x\times y:\alpha (x-1)+\beta (y-1)<0\},$$ where $\alpha$ and $\beta$ are non-negative real numbers such that $\alpha +\beta >0$. Notice that $K_0\subset H\cap ([1/2,a]\times [1/2,b])$, so $\max \{a,b\}>3/2$, for otherwise $$1/2\le n/4\le \text{area }{K}_0<\text{area}(H\cap ([1/2,3/2]\times [1/2,3/2]))=1/2,$$ which is a contradiction – the strict inequality above is due to the fact that $K_0$ is closed. Without loss of generality, assume that $a>3/2$, so $\beta \ne 0$ and $$\begin{array}{rl}\text{area }{K}_0<\text{area}(H\cap ([1/2,a]\times [1/2,\infty )))& \\ & =\frac{1}{2}\left(a-\frac{1}{2}\right)\left(1-\frac{\alpha }{\beta }\left(a-\frac{3}{2}\right)\right)\le \frac{1}{2}\left(a-\frac{1}{2}\right);\end{array}$$ as before, the inequality is strict because $K_0$ is closed. Finally, recall that $a-1/2<n/2$ and $\text{area }{K}_0\ge n/4$ to derive a contradiction.