While brushing up on my old discrete mathematics skills I stumbled upon this problem that I can't solve.
In $\mathbb{R^2}$ the middle point of two coordinates is $(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2})$. Show that given five points in $\mathbb{Z^2}$ (points with intetger coordinates) there are at least one pair of them whose middle point also lays in $\mathbb{Z^2}$. Let us consider the corresponding question in $\mathbb{R^3}$. How many points in $\mathbb{Z^3}$ would you need to be sure that at least one pair of them has a middle point in $\mathbb{Z^3}$?
I am thinking that using the pigeonhole principle is appropriate, how I would use it is unclear to me though.
$\mathbb{Z^2}$" />
Best Answer
Let $(x_i,y_i), i = 1,2,3,4,5$ be those $5$ points.
Consider the parity of each $x_i, y_i$. There are four possible combinations:
Odd-odd, odd-even, even-odd, even-even.
By pigeonhole principle, at least $2$ points are in the same category.
Since odd-odd=even and even-even=even, the two points in the same category will have a midpoint in $\mathbb Z^2$ (since the difference of the points in both coordinates are divisible by $2$)
Can you see how this generalizes to higher dimensions?