Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 USAMO Problems/Problem 5"

(→‎Solution (INCOMPLETE))
(→‎Solution (INCOMPLETE))
Line 14: Line 14:
  
 
The largest distance between any two points in the entire grid is <math>\sqrt{2}\left(2^{k+1} - 1\right) < c^{k+3}</math> for all <math>c\ge 2.</math> Therefore, the label <math>L</math> cannot be used anywhere else in the grid. However, <math>B, C,</math> and <math>D</math> each require at least <math>k+3</math> distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in <math>A.</math> It follows that the entire grid requires at least <math>k+4</math> distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any <math>c\ge 2.</math>
 
The largest distance between any two points in the entire grid is <math>\sqrt{2}\left(2^{k+1} - 1\right) < c^{k+3}</math> for all <math>c\ge 2.</math> Therefore, the label <math>L</math> cannot be used anywhere else in the grid. However, <math>B, C,</math> and <math>D</math> each require at least <math>k+3</math> distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in <math>A.</math> It follows that the entire grid requires at least <math>k+4</math> distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any <math>c\ge 2.</math>
 +
 +
I have heard from others that the actual bound is <math>c=\sqrt{2},</math> i.e. a labeling as desired exists for <math>c\le\sqrt{2}</math> and does not exist for <math>c\ge\sqrt{2}.</math> I think achieving this bound from the lower end requires some significantly non-trivial labeling. The inductive argument above seems fairly loose, so I think that it can be sharpened to bring the upper bound down to <math>\sqrt{2},</math> but I am not sure yet how exactly to do so.

Revision as of 02:07, 3 May 2017

Problem

Let $\mathbf{Z}$ denote the set of all integers. Find all real numbers $c > 0$ such that there exists a labeling of the lattice points $( x, y ) \in \mathbf{Z}^2$ with positive integers for which: only finitely many distinct labels occur, and for each label $i$, the distance between any two points labeled $i$ is at least $c^i$.

Solution (INCOMPLETE)

For $c\le 1,$ we can label every lattice point $1.$ For $c\le 2^{1/4},$ we can make a "checkerboard" labeling, i.e. label $(x, y)$ with $1$ if $x+y$ is even and $2$ if $x+y$ is odd. One can easily verify that these labelings satisfy the required conditions. Therefore, a labeling as desired exists for all $0 < c\le 2^{1/4}.$

We now prove that no labeling as desired exists for any $c\ge 2.$ To do this, we will prove that labeling a $2^k$-by-$2^k$ square grid of lattice points requires at least $k+3$ distinct labels for all natural numbers $k$; 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, $k=1,$ we have four points in a square of side length $1.$ The maximum distance between any two of these points is $\sqrt{2} < c^1$ for all $c\ge 2,$ so all four points must have different labels. This completes the base case.

Now, for the inductive step, suppose that labeling a $2^k$-by-$2^k$ square grid of lattice points requires at least $k+3$ distinct labels for some natural number $k.$ We will now prove that labeling a $2^{k+1}$-by-$2^{k+1}$ square grid of lattice points requires at least $k+4$ distinct labels.

Take a $2^{k+1}$-by-$2^{k+1}$ square grid of lattice points. Divide this grid into four quadrants, $A, B, C,$ and $D.$ By the inductive hypothesis, $A$ requires at least $k+3$ distinct labels. At least one of these labels must be $k+3$ or greater; take one such label and call it $L.$

The largest distance between any two points in the entire grid is $\sqrt{2}\left(2^{k+1} - 1\right) < c^{k+3}$ for all $c\ge 2.$ Therefore, the label $L$ cannot be used anywhere else in the grid. However, $B, C,$ and $D$ each require at least $k+3$ distinct labels as well by the inductive hypothesis. Thus, they must use at least one label that is not used in $A.$ It follows that the entire grid requires at least $k+4$ distinct labels. This completes the inductive step, and thus we conclude that no labeling as desired exists for any $c\ge 2.$

I have heard from others that the actual bound is $c=\sqrt{2},$ i.e. a labeling as desired exists for $c\le\sqrt{2}$ and does not exist for $c\ge\sqrt{2}.$ I think achieving this bound from the lower end requires some significantly non-trivial labeling. The inductive argument above seems fairly loose, so I think that it can be sharpened to bring the upper bound down to $\sqrt{2},$ but I am not sure yet how exactly to do so.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAMO_Problems/Problem_5&oldid=85518"