Given any 9 lattice points in space, show that we can find two which have a lattice point on the interior of the segment joining them.
We can divide the points into 8 categories according to the parity of each coordinate. There must be at least 2 points in the same category. The midpoint of the line joining them is then also a lattice point.
Comment. If you have not seen this trick before, the question is hard.
32nd Putnam 1971
© John Scholes
27 Jan 2001