## Monday, May 8, 2006

### Find That Lattice Point. Topic: Number Theory. Level: AIME/Olympiad.

Problem: (Minkowski's Thoerem) Any bounded plane convex region $R$ symmetrical about the origin with area $> 4$ contains at least two other lattice points other than the origin itself.

Solution: WLOG, assume the lattice is a regular square lattice (with side length $1$, of course). The result can easily be generalized to different types of lattices.

Consider partitioning the lattice into $2 \times 2$ squares (with the origin being the vertex of four of them). Since the area of $R$ is greater than $4$, we can find two points in $R$ such that their coordinates relative to the $2 \times 2$ squares they are in are equivalent (consider stacking all the $2 \times 2$ squares up; there must exist a point directly above another one or the area is $\le 4$).

Call these points

$P(2a+\alpha, 2b+\beta)$ and $Q(2c+\alpha, 2d+\beta)$

with $a,b,c,d$ integers and $0 \le \alpha, \beta \le 2$ reals. But since $R$ is symmetrical about the origin, we know

$P^{\prime}(-2a-\alpha, -2b-\beta)$ and $Q^{\prime}(-2c-\alpha, -2d-\beta)$

also exist in $R$. If $R$ is convex, then any point along a line segment connecting two points in $R$ is also in $R$. In particular, the midpoint of any line segment between two points in $R$ is in $R$. Hence the midpoints of $PQ^{\prime}$ and $P^{\prime}Q$ are in $R$. They are

$M_1(a-c, b-d)$ and $M_2(c-a, d-b)$,

which are lattice points not on the origin because $a,b,c,d$ are integers and $P \neq Q$. Therefore $R$ contains at least two other lattice points $M_1$ and $M_2$. QED.

--------------------

Comment: We could have invoked symmetry at the end to find $M_2$ from $M_1$, too. From the proof, it shouldn't be too hard to tell what I assumed at the beginning for other lattices; basically you just need to define a coordinate system with the same properties . I first encountered this problem at PROMYS and it appears in most Number Theory texts, as far as I know.

--------------------

Practice Problem: Can you generalize this result to a $3$-space? An $n$-space?