Two points $(c, d, e),(x, y, z) \in \mathbb{R}^3$, we say that the midpoint of these two points is the point with coordinates $\left(\frac{c+x}{2} , \frac{d+y}{2} , \frac{e+z}{2}\right)$

Take any set $S$ of nine points from $\mathbb{R}^3$ with integer coordinates.

Prove that there must be at least one pair of points in $S$ whose midpoint also has integer coordinates.

I've tried to do an example with set $$S=\{(2,2,2),(1,8,2),(3,4,5),(5,2,2),(4,2,9),\\(2,1,4),(6,8,2),(0,0,0),(5,2,3)\}$$

So taking $2$ points, $(3,4,5)$ and $(5,2,3)$ so $(3+5)/2=4$, $(4+2)/2=3$, $(5+3)/2 = 4$, which are integers. I'm wanting this argument to hold in general and I'm finding it tricky to prove this does anyone have suggestions would be grateful!

  • 12
    $\begingroup$ These are 3-tuples. You can look at each individual coordinate as being either even (e) or odd (o). So for example, point 1 could be (e,e,e) and point 2 could be (o,o,e) and so on.... Look at all possible cases (how many possible cases?) and then ask yourself, when would two points give integer midpoints using the formula you provided? Finally, think to yourself, if I have 9 points....... since its a discrete math class, you probably learned about a particular "principle"... $\endgroup$ – Eleven-Eleven Oct 8 '18 at 12:21
  • 5
    $\begingroup$ pigeon hole principle is probably onto the right track ? $\endgroup$ – sphynx888 Oct 8 '18 at 12:32
  • 8
    $\begingroup$ By the way, a big +1 for doing an example and seeing what happened. A good next step might have been to try to build a counterexample, and seeing where you got stuck --- that might have given further insight. $\endgroup$ – John Hughes Oct 8 '18 at 12:47

Just to reiterate what I said earlier, if we list the possible coordinate parities of the $3$-tuples, we have


So there are $8$ different parity $3$-tuples possible. Also note the addition of even and odd integers;

$$e+e=e,$$ $$o+o=e,$$ $$e+o=o$$

So in order for your midpoint to be an integer, we need to have the points being added to have coordinates of the same parity. Therefore, since we have 9 points, assuming our first 8 points are all of different parity combinations as above, the 9th must be one of these 8 possibilities. If you add up the two points that have the same coordinate parity structure, this will yield an even number, which is divisible by 2. For example, if both ordered triples have coordinate parity structure $(e,e,o)$, then by the midpoint formula,

$$Mid((e,e,o),(e,e,o))=\left(\frac{e+e}{2}, \frac{e+e}{2},\frac{o+o}{2}\right)=\left(\frac{2e}{2}, \frac{2e}{2},\frac{2o}{2}\right)=(e,e,o)$$

And so by the Pigeonhole principle, there is at least 1 midpoint that contains integer coordinates. And as Robert Z noted in his solutions, this can be extended to $n$-tuples as well.


Hint. Read carefully Eleven-Eleven's comment (or take a look at Pigeon-Hole Principle and 2d grid?) and, by using the Pigeonhole Principle, show the following more general statement: in any set of $2^n+1$ points in $\mathbb{Z}^n$ there is at least one pair that has the midpoint in $\mathbb{Z}^n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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