Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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...

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.