Difference between revisions of "2017 USAMO Problems/Problem 5"
(→Solution (INCOMPLETE)) |
(→Solution (INCOMPLETE)) |
||
| Line 5: | Line 5: | ||
For <math>c\le 1,</math> we can label every lattice point <math>1.</math> For <math>c\le 2^{1/4},</math> we can make a "checkerboard" labeling, i.e. label <math>(x, y)</math> with <math>1</math> if <math>x+y</math> is even and <math>2</math> if <math>x+y</math> is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all <math>0 < c\le 2^{1/4}.</math> | For <math>c\le 1,</math> we can label every lattice point <math>1.</math> For <math>c\le 2^{1/4},</math> we can make a "checkerboard" labeling, i.e. label <math>(x, y)</math> with <math>1</math> if <math>x+y</math> is even and <math>2</math> if <math>x+y</math> is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all <math>0 < c\le 2^{1/4}.</math> | ||
| − | An iterated version of the checkerboard labeling can actually work for all values <math>c < \sqrt{2}.</math> For convenience, define the | + | An iterated version of the checkerboard labeling can actually work for all values <math>c < \sqrt{2}.</math> For convenience, define the **original lattice grid** to be the set of all lattice points in the coordinate plane. Define a modified lattice grid of size <math>x</math> to be a structure similar to the lattice points on the coordinate plane, but with the minimum separation between any two points equaling <math>x</math> (as opposed to <math>1</math>). On the first step, assign a label <math>1</math> to half of the points in a checkerboard arrangement. One can see that the points that have not yet been labeled form a modified lattice grid of size <math>\sqrt{2}</math> (this lattice grid is also rotated by <math>45^{\circ}</math> from the original lattice grid). At this point, for the second step, assign a label <math>2</math> to half of the points, again in a checkerboard arrangement. At this point, the points that have not yet been labeled form a modified lattice grid of size <math>2</math> (and again, it is rotated <math>45^{\circ}</math> from the modified lattice grid after the first step). One then continues in this fashion. After the <math>N^{\text{th}}</math> step (where <math>N</math> is a natural number), the points that have not yet been labeled form a modified lattice grid with size <math>\left(\sqrt{2}\right)^N.</math> Since <math>c < \sqrt{2},</math> we will eventually have <math>\left(\sqrt{2}\right)^N > c^{n+1}</math> for some sufficiently large <math>N.</math> At this point, we can label all remaining points in the original lattice grid <math>N+1,</math> and this produces a labeling of all of the lattice points in the plane that satisfies all of the conditions. Therefore, a labeling as desired exists for all <math>c < \sqrt{2}.</math> |
We now prove that no labeling as desired exists for any <math>c\ge 2.</math> To do this, we will prove that labeling a <math>2^k</math>-by-<math>2^k</math> square grid of lattice points requires at least <math>k+3</math> distinct labels for all natural numbers <math>k</math>; hence for a sufficiently large section of the lattice plane the number of distinct labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many distinct labels. We will prove this using induction. | We now prove that no labeling as desired exists for any <math>c\ge 2.</math> To do this, we will prove that labeling a <math>2^k</math>-by-<math>2^k</math> square grid of lattice points requires at least <math>k+3</math> distinct labels for all natural numbers <math>k</math>; hence for a sufficiently large section of the lattice plane the number of distinct labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many distinct labels. We will prove this using induction. | ||
Revision as of 16:18, 3 May 2017
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 
An iterated version of the checkerboard labeling can actually work for all values 
For convenience, define the **original lattice grid** to be the set of all lattice points in the coordinate plane. Define a modified lattice grid of size 
to be a structure similar to the lattice points on the coordinate plane, but with the minimum separation between any two points equaling (as opposed to ). On the first step, assign a label to half of the points in a checkerboard arrangement. One can see that the points that have not yet been labeled form a modified lattice grid of size 
(this lattice grid is also rotated by 
from the original lattice grid). At this point, for the second step, assign a label to half of the points, again in a checkerboard arrangement. At this point, the points that have not yet been labeled form a modified lattice grid of size (and again, it is rotated from the modified lattice grid after the first step). One then continues in this fashion. After the 
step (where 
is a natural number), the points that have not yet been labeled form a modified lattice grid with size 
Since 
we will eventually have 
for some sufficiently large 
At this point, we can label all remaining points in the original lattice grid 
and this produces a labeling of all of the lattice points in the plane that satisfies all of the 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 
distinct labels for all natural numbers 
; hence for a sufficiently large section of the lattice plane the number of distinct labels required grows arbitrarily large, so the entire lattice plane cannot be labeled with finitely many distinct labels. We will prove this using induction.
For the base case, 
we have four points in a square of side length The maximum distance between any two of these points is 
for all 
so all four points must have different labels. This completes the base case.
Now, for the inductive step, suppose that labeling a -by- square grid of lattice points requires at least distinct labels for some natural number 
We will now prove that labeling a 
-by- square grid of lattice points requires at least 
distinct labels.
Take a -by- square grid of lattice points. Divide this grid into four quadrants, 
and 
By the inductive hypothesis, 
requires at least distinct labels. At least one of these labels must be or greater; take one such label and call it 
The largest distance between any two points in the entire grid is 
for all Therefore, the label 
cannot be used anywhere else in the grid. However, 
and 
each require at least distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in 
It follows that the entire grid requires at least distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any
I have heard from others that the actual boundary is 
This makes intuitive sense, since the iterated checkerboard labeling outlined above just breaks down at this value (you will be able to get closer and closer to labeling all of the lattice points, but you can never get there, since you will never have ). The inductive argument above seems fairly loose, so I think that it can be sharpened to bring the upper bound down to 
but I am not sure yet how exactly to do so. I think the way to do it is to somehow force new labels (instead of just ) each time you double the side length of the square grid.
