Show that given five points in $\mathbb{Z^2}$ there are at least one pair of them whose middle point also lies in $\mathbb{Z^2}$

Question

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}$" />

Answer 1

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?

Answer 2

Let $P=(a,b)$ and $Q=(c,d)$ be two points in $\mathbb{Z}^2$. The midpoint will itself be in $\mathbb{Z}^2$ if and only if the two pairs of numbers $(a,c)$ and $(b,d)$ have both the same parity.

Since there are only four possibilities of pairing parities, as soon as you have a 5th point you must have two of the same parities.

Thus the answer comes from an application of the pigeonhole principle.

Answer 3

Let $\mathcal{P}$ be your set of points and consider a map $f:\mathcal{P}\rightarrow \{\pm 1\}^2$, where $f(x,y)$ is the tuple with the parity of each coordinate, e.g. $f(3,2)=(-,+)$. Then $|\mathcal{P}|=5> |\{\pm 1\}^2|=4$, so by the pigeonhole principle you will have at least two points with the same parity tuple. So their midpoint has integer coordinates.

For three dimensions you want to look at $\{\pm 1\}^3$, what is the cardinality of this set? This will tell you the necessary size for $\mathcal{P}$.