"Let (x, y, z) ∈ R^3 be a point with integer coordinates. Show that if we choose 9 such points then the midpoint of at least one pair of these points has integer coordinates."
Hi everyone, I'm Matt. I'm a student at the University of Melbourne, majoring in Discrete Mathematics and Operations Research. The quote above was question 3a on my Discrete Maths exam last year.
Whenever I tell someone I'm studying Maths, there's a fifty-percent chance I immediately face the response: "Oh, I HATED Maths in high school!"
I'm not sure exactly why so many people didn't enjoy the subject (or why they think it's appropriate to tell me how much they hate one of my favourite things). In a spirit of educating the masses (or possibly sharing the pain), I've decided to show how I solved the problem.
First off, some definitions. Integers are whole numbers, like 5, 0, or -3. A point in R^3 is a set of three coordinates, defining a spot in 3D space. If the point (x, y, z) has integer coordinates, x, y, and z are all integers.
The midpoint of (x, y, z) and (a, b, c) is the sum of both points divided by 2. The sum of the points is (x+a, y+b, z+c), and if half of the sum is integer-valued, the sum must be even-valued. That is, x+a, y+b and z+c are all even.
Suddenly our geometry problem has become a parity problem. We know from primary school that two evens make an even, two odds make an even, and an even and an odd make an odd. Therefore, for x+a to be even, x and a must both be even or both be odd - they must have the same parity. The same is true for y and b, and z and c. This means that (x, y, z) and (a, b, c) must have the same three-dimensional parity.
In one dimension, there are two parities: even and odd. In two dimensions there are four: even-even, even-odd, odd-even, odd-odd. In three dimensions, there are eight different parities, but we have nine points.
The "Pigeonhole Principle" states that if we have N pigeonholes and N+1 pigeons, at least two pigeons must be in the same hole. More specifically, if we have 9 points and eight possible parities, at least two points MUST have the same parity. This means the sum of those points MUST be even-valued, and therefore the midpoint MUST be integer-valued - and there's our proof.
Thanks for reading!
Matt S.
Melbourne, Australia