2006 SMT/Advanced Topics Problems/Problem 7
Problem
A lattice point in the plane is a point whose coordinates are both integers. Given a set of distinct lattice points in the plane, find the smallest number of line segments
for which
and
are distinct lattice points in this set and the midpoint of
is also a lattice point (not necessarily in the set).
Solution
Note that if the midpoint of is a lattice point, then the
and
coordinates of
must have the same parity as the respective coordinates in
. Let
denote an odd coordinate and
denote an even coordinate. Therefore, we have four cases:
. Let
be the number of coordinates in the first case,
be the number of coordinates in the second case,
be the number of coordinates in the third case, and
be the number of coordinates in the fourth case.
Notice that . The number of line segments whose midpoint is a lattice point is therefore
.
From QM-AM, we have , and so
, and so the minimum value of
is
.