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 $100$ distinct lattice points in the plane, find the smallest number of line segments $\overline{AB}$ for which $A$ and $B$ are distinct lattice points in this set and the midpoint of $\overline{AB}$ is also a lattice point (not necessarily in the set).

Solution

Note that if the midpoint of $\overline{AB}$ is a lattice point, then the $x$ and $y$ coordinates of $A$ must have the same parity as the respective coordinates in $B$ . Let $o$ denote an odd coordinate and $e$ denote an even coordinate. Therefore, we have four cases: $(o,o); (o,e); (e,o); (e,e)$ . Let $a$ be the number of coordinates in the first case, $b$ be the number of coordinates in the second case, $c$ be the number of coordinates in the third case, and $d$ be the number of coordinates in the fourth case.

Notice that $a+b+c+d=100$ . The number of line segments whose midpoint is a lattice point is therefore $\binom{a}{2}+\binom{b}{2}+\binom{c}{2}+\binom{d}{2}=\frac{1}{2}(a^2-a+b^2-b+c^2-c+d^2-d)$

$=\frac{1}{2}(a^2+b^2+c^2+d^2-100)$ .

From QM-AM, we have $\sqrt{\frac{a^2+b^2+c^2+d^2}{4}}\ge\frac{a+b+c+d}{4}=25$ , and so $a^2+b^2+c^2+d^2\ge4\cdot25^2=2500$ , and so the minimum value of $\frac{1}{2}(a^2+b^2+c^2+d^2-100)$ is $\frac{1}{2}(2500-100)=\boxed{1200}$ .

Page

Toolbox

Search

2006 SMT/Advanced Topics Problems/Problem 7

Problem

Solution

See Also