Romania — 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'$ 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' = \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'$. Indeed, if $K'$ contained one such, say $i \times j$, then the line $y = j$ would intersect $K'$ 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'$ about the horizontal line $y = 1/2$. The resulting image $K''$ 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'' = \text{area } K' = \text{area } K \ge n$. Then if $K$ contains no lattice point, so does $K''$.

Now let $a = \sup\{x : x \times 1/2 \in K''\}$ and $b = \sup\{y : 1/2 \times y \in K''\}$ and notice that $a - 1/2 < n/2$ and $b - 1/2 < n/2$ – both inequalities are strict, for $K''$ is closed. Let further $K_0 = K'' \cap \{x \times y : x \ge 1/2 \text{ and } y \ge 1/2\}$ be the upper right quarter of $K''$. Clearly, $K_0$ is a closed convex set, and $\text{area } K_0 = (\text{area } K'')/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{aligned} \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{aligned}$$
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.