# Midpoints of segments joining lattice points

Show that, given $2^n+1$ points with integer coordinates in $\mathbb R^n$, there exists a pair of points among them such that all the co-ordinates of the midpoint of the line segment joining them are integers.

-
Could you improve the title, also I don't think number theory (elementary or not) has anything to do with this question; it seems combinatorial in its nature. – Asaf Karagila May 4 '11 at 14:38
The solution relies on the distinction between even and odd, so, it's number theory. – Gerry Myerson May 5 '11 at 1:01
The case $n=3$ was problem A-1 on the 1971 Putnam exam. – Gerry Myerson May 5 '11 at 1:02
@Gerry Myerson, Thanks for the information, I also acknowledge it is a number theory problem. – Bhaskar Dey May 5 '11 at 6:32

Temporarily, let us call two points $(x_1, \dots, x_n)$ and $(y_1,\dots,y_n)$ of $\mathbb{Z}^n$ equivalent if $x_i$ and $y_i$ have the same parity for all $i$.

There are exactly $2^n$ equivalence classes, one for each sequence of $0$s and $1$s of length $n$.

If we are given $2^n+1$ points of $\mathbb{Z}^n$, there must be, by the Pigeonhole Principle, a pair of points that fall in the same equivalence class.

Call these points $P$ and $Q$. The midpoint of $PQ$ has integer coordinates.

-

Hint: The limiting condition here is based on the parity of the coordinates. For example, if two points have even ith components, then the ith component of their midpoint will be an integer (or odd - but it will not be an integer if one is even and one is odd).

Second Hint: Prove this using parity for low dimensions to get a feel for how it works.

-

You can start with $n=1$, where it says given three points in $\mathbb{R}$, you can find two of them that differ by an even number. Can you prove that? Then for $n=2$, you are given five points. If you can find three with first coordinates of the same parity...

-
Nice hint.   – Did May 4 '11 at 14:17
@Didier: but, thinking about it, it leads to an inductive proof. There is also a direct one available that mixedmath hints at. – Ross Millikan May 4 '11 at 14:48