2017 USAMO Problems/Problem 5
Problem
Let denote the set of all integers. Find all real numbers
such that there exists a labeling of the lattice points
with positive integers for which: only finitely many distinct labels occur, and for each label
, the distance between any two points labeled
is at least
.
Solution (INCOMPLETE)
For we can label every lattice point
For
we can make a "checkerboard" labeling, i.e. label
with
if
is even and
if
is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all
We now prove that no labeling as desired exists for any To do this, we will prove that labeling a
-by-
square grid of lattice points requires at least
labels for all natural numbers
; hence for a sufficiently large section of the lattice plane the number of labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many labels. We will prove this using induction.