Let $n$ be an integer number greater than or equal to $2$, and let $K$ be a closed convex set of area greater than or equal to $n$, contained in the open square $(0, n) \times (0, n)$. Prove that $K$ contains some point of the integral lattice $\mathbb{Z} \times \mathbb{Z}$. Marius Cavachi
Problem
Source: Romania TST 2 2010, Problem 4
Tags: geometry, calculus, integration, algebra, function, domain, similar triangles
11.09.2012 01:23
Consider a minimal $n$ such that $\text{Area}(K)\ge n$, but $K$ contained no lattice points. The lattice points divide the square into $n$ columns and $n$ rows. If $K$ did not intersect every column nor every row, then $K$ could be placed inside a square of dimension $(0,n-1)\times (0,n-1)$ contradicting the choice of $n$, so wlog $K$ intersect every column (1). Let $\ell_{\alpha}$ denote the line $x = \alpha$, and let $f(x)$ denote the length of the line $K \cap \ell_x$ for $x \in (0,n)$. From (1), $f$ is non-zero over an interval $(a,b)$ of length greater than $n-2$. Specifically $\textstyle \int_{a}^{b} f(x) dx = \text{Area}(K)$. Lemma 1: $f$ is concave Proof: Take any points $x,y\in(a,b)$ and let $X_1,X_2,Y_1,Y_2$ be the four points at which the boundary $\partial K$ intersects $\ell_x$ and $\ell_y$ respectively. Since $K$ is convex the chords $X_1Y_1$ and $X_2Y_2$ lie inside $K$, so $f(tx+(1-t)y) \ge tf(x) + (1-y)f(y)$ for all $t\in(0,1)$. That is, $f$ is concave $\square$. $f$ is positive and concave on an $(a,b)$. Further $f(m) < 1$ for $m=(a,b)\cap \mathbb{N}$ because $K$ contains no lattice points. Therefore $f(x) > 1$ can only occur in one interval $(i,i+1)$ for some integer $i$. Now draw two lines, $l_i, l_{i+1}$ through $(i,1)$ and $(i+1,1)$ respectively that are tangent to $f$. Then let $L$ be the triangle formed by $l_i, l_{i+1}$ and the $x$-axis. $f$ lies completely within this triangle. Further the domain of $f$ is inside $(0,n)$ so comparing this triangle with the box $(0,n)\times (0,1)$ and using similar triangles to bound the area it can be shown that $\textstyle \int_{a}^{b} f(x) dx < n$. (see attachment) This contradicts the assumption that $\text{Area}(K) \ge n$, so no minimal counter-example exists $\square$
Attachments: