Maths WorkshopMaths problems with full solutions
Exercise 1098Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Integer grid points

#pigeonhole#grid#midpoints

Statement

Show that among any 55 integer lattice points in the plane, two have a midpoint with integer coordinates.

Hint

Classify points by the parities of their coordinates: 44 classes.

Show solutionHide solution

Solution

Classes. Each lattice point has coordinate parities in {(even,even),(even,odd),(odd,even),(odd,odd)}\{(\text{even},\text{even}),(\text{even},\text{odd}),(\text{odd},\text{even}),(\text{odd},\text{odd})\} — 44 classes.

Pigeonhole. 55 points in 44 classes: two share the same class.

Midpoint. If two points have the same parity in both coordinates, their sum has even coordinates, so their midpoint is a lattice point.

Conclusion. Two points have a lattice midpoint.