Difference between revisions of "2017 USAMO Problems/Problem 5"
(→Solution (INCOMPLETE)) |
(→Solution (INCOMPLETE)) |
||
| Line 7: | Line 7: | ||
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> labels for all natural numbers <math>k</math>; 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. | 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> labels for all natural numbers <math>k</math>; 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. | ||
| − | For the base case, <math>k=1,</math> we have four points in a square of side length <math>1.</math> The maximum distance between any two of these points is <math>\sqrt{2} < | + | For the base case, <math>k=1,</math> we have four points in a square of side length <math>1.</math> The maximum distance between any two of these points is <math>\sqrt{2} < c^1</math> for all <math>c\ge 2,</math> so all four points must have different labels. This completes the base case. |
Now, for the inductive step, suppose that labeling a <math>2^k</math>-by-<math>2^k</math> square grid of lattice points requires at least <math>k+3</math> labels for some natural number <math>k.</math> We will now prove that labeling a <math>2^{k+1}</math>-by-<math>2^{k+1}</math> square grid of lattice points requires at least <math>k+4</math> labels. | Now, for the inductive step, suppose that labeling a <math>2^k</math>-by-<math>2^k</math> square grid of lattice points requires at least <math>k+3</math> labels for some natural number <math>k.</math> We will now prove that labeling a <math>2^{k+1}</math>-by-<math>2^{k+1}</math> square grid of lattice points requires at least <math>k+4</math> labels. | ||
| + | |||
| + | Take a <math>2^{k+1}</math>-by-<math>2^{k+1}</math> square grid of lattice points. The largest distance between any two points in this grid is <math>\sqrt{2}\left(2^{k+1} - 1\right) < c^{k+3}</math> for all <math>c\ge 2.</math> | ||
Revision as of 01:56, 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 
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.
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 labels for some natural number 
We will now prove that labeling a 
-by- square grid of lattice points requires at least 
labels.
Take a -by- square grid of lattice points. The largest distance between any two points in this grid is 
for all
