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.
Midpoints of segments joining lattice points
-
0@Gerry Myerson, Thanks for the information, I also acknowledge it is a number theory problem. – 2011-05-05
3 Answers
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.
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...
-
0@Didier: but, thinking about it, it leads to an inductive proof. There is also a direct one available that mixedmath hints at. – 2011-05-04
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.