Plot five points at random at the intersections of a coordinate grid. Between each pair of points a line segment can be drawn.

Prove that the midpoint of at least one of these segments occurs at an intersection of grid lines.

Each coordinate of a grid point is either odd or even, making four possible parities for a point: (odd, odd), (odd, even), (even, odd), and (even, even).

(odd+odd)/2 and (even+even)/2 are both integers. This implies given two grid points with the same parity then their midpoint must also be on a grid point.

Because there are five given points in all then there must exist at least one pair whose parities match and subsequently that midpoint must be a grid point.