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))
 
(21 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
Let <math>\mathbf{Z}</math> denote the set of all integers. Find all real numbers <math>c > 0</math> such that there exists a labeling of the lattice points <math>( x, y ) \in \mathbf{Z}^2</math> with positive integers for which: only finitely many distinct labels occur, and for each label <math>i</math>, the distance between any two points labeled <math>i</math> is at least <math>c^i</math>.
 
Let <math>\mathbf{Z}</math> denote the set of all integers. Find all real numbers <math>c > 0</math> such that there exists a labeling of the lattice points <math>( x, y ) \in \mathbf{Z}^2</math> with positive integers for which: only finitely many distinct labels occur, and for each label <math>i</math>, the distance between any two points labeled <math>i</math> is at least <math>c^i</math>.
  
−
==Solution (INCOMPLETE)==
 
−
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>
 
  
−
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.
+
==Solution 1 (Evan Chen, Calvin Deng)==
 +
See page 11 of this PDF:
 +
https://web.evanchen.cc/exams/USAMO-2017-notes.pdf
 +
 
 +
 
 +
==Solution 2 (INCOMPLETE)==
 +
For <math>c\le 1,</math> we can label every lattice point <math>1.</math> For <math>c\le \sqrt[4]{2},</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 \sqrt[4]{2}.</math>
 +
 
 +
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. For the <math>N^{\text{th}}</math> step, the points we are labeling are separated by at least <math>\sqrt{2}\times\left(\sqrt{2}\right)^{N-1} = \left(\sqrt{2}\right)^N > c^N,</math> so we know that our labeling at each step is acceptable.
 +
 
 +
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.
 +
 
 +
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> distinct 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> distinct labels.
 +
 
 +
Take a <math>2^{k+1}</math>-by-<math>2^{k+1}</math> square grid of lattice points. Divide this grid into four quadrants, <math>A, B, C,</math> and <math>D.</math> By the inductive hypothesis, <math>A</math> requires at least <math>k+3</math> distinct labels. At least one of these labels must be <math>k+3</math> or greater; take one such label and call it <math>L.</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 boundary is <math>\sqrt{2}.</math> 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 <math>\left(\sqrt{2}\right)^N > c^{N+1}</math>). 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. I think the way to do it is to somehow force <math>2</math> new labels (instead of just <math>1</math>) each time you double the side length of the square grid.
 +
 
 +
==Solution 3==
 +
We claim that for all <math>c<\sqrt{2}</math>, there exists such a configuration.
 +
 
 +
Lemma 1a: If there exists a configuration for <math>c=c_1</math>, then for any <math>c_2\le{c_1}</math>, there also exists a configuration for <math>c=c_2</math>.
 +
Note that any labeling that can be done for <math>c=c_1</math> exists for <math>c=c_2</math>. Thus, we may copy the configuration from <math>c=c_1</math> to <math>c=c_2</math>.
 +
 
 +
Lemma 1b: If there does not exist a configuration for <math>c=c_1</math>, then for any <math>c_2\ge{c_1}</math>, there does not exist a configuration for <math>c=c_2</math>.
 +
Note that any labeling which may be done for <math>c=c_2</math> should also be available for <math>c=c_1</math>. However, we already stated that <math>c=c_1</math> has no configuration, and so <math>c=c_2</math> doesn't either.
 +
 
 +
We now prove that <math>c=\sqrt{2}</math> does not work. WLOG, label the origin of our lattice plan with label <math>1</math>. WLOG, we can cover every point that we can with label <math>1</math> because not labeling any such possible point does not affect the distance between points that aren't allowed to be labelled.
 +
 
 +
Name the state of the lattice grid before using label <math>1</math> state <math>S</math>. After covering every point possible, we are left with only lattice points that have coordinates that sum to an odd integer. Notice, however, that if we discard the covered points and rotate all the new points by <math>\frac{\pi}{4}</math> radians counterclockwise, we end up with the same grid as state <math>S</math>, only all the distances are multiplied by scalar <math>\sqrt{2}</math>. However, before placing label <math>2</math>s, note that we are in the same state <math>S</math> as before, because our minimum distance is also multiplied by scalar <math>\sqrt{2}</math>. Thus, we will always be in an infinite loop, stuck in state <math>S</math>, and thus it is impossible to complete the labeling.
 +
 
 +
It suffices to show that any <math>c=2^{k}</math> works given <math>k<0.5</math>. Note that the two smallest distances between any two points in the starting grid are <math>1</math> and <math>\sqrt{2}</math>. When we are currently in state <math>S</math> using label <math>I</math>, it is obvious that if <math>2ki-i\le{1}</math>, we can break out of state <math>S</math> (Our effective minimum length would be at most 1, and we can cover every remaining point). Because <math>k<0.5</math>, there does exist an <math>I</math> where this occurs. Thus, any <math>c<\sqrt{2}</math> works, hence proved. <math>\blacksquare{}</math> ~SigmaPiE

Latest revision as of 11:19, 17 July 2023

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 1 (Evan Chen, Calvin Deng)

See page 11 of this PDF: https://web.evanchen.cc/exams/USAMO-2017-notes.pdf


Solution 2 (INCOMPLETE)

For $c\le 1,$ we can label every lattice point $1.$ For $c\le \sqrt[4]{2},$ 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 \sqrt[4]{2}.$

An iterated version of the checkerboard labeling can actually work for all values $c < \sqrt{2}.$ 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 $x$ to be a structure similar to the lattice points on the coordinate plane, but with the minimum separation between any two points equaling $x$ (as opposed to $1$).

On the first step, assign a label $1$ 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 $\sqrt{2}$ (this lattice grid is also rotated by $45^{\circ}$ from the original lattice grid). At this point, for the second step, assign a label $2$ 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 $2$ (and again, it is rotated $45^{\circ}$ from the modified lattice grid after the first step). One then continues in this fashion. For the $N^{\text{th}}$ step, the points we are labeling are separated by at least $\sqrt{2}\times\left(\sqrt{2}\right)^{N-1} = \left(\sqrt{2}\right)^N > c^N,$ so we know that our labeling at each step is acceptable.

After the $N^{\text{th}}$ step (where $N$ is a natural number), the points that have not yet been labeled form a modified lattice grid with size $\left(\sqrt{2}\right)^N.$ Since $c < \sqrt{2},$ we will eventually have $\left(\sqrt{2}\right)^N > c^{N+1}$ for some sufficiently large $N.$ At this point, we can label all remaining points in the original lattice grid $N+1,$ 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 $c < \sqrt{2}.$

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 boundary is $\sqrt{2}.$ 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 $\left(\sqrt{2}\right)^N > c^{N+1}$). 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. I think the way to do it is to somehow force $2$ new labels (instead of just $1$) each time you double the side length of the square grid.

Solution 3

We claim that for all $c<\sqrt{2}$, there exists such a configuration.

Lemma 1a: If there exists a configuration for $c=c_1$, then for any $c_2\le{c_1}$, there also exists a configuration for $c=c_2$. Note that any labeling that can be done for $c=c_1$ exists for $c=c_2$. Thus, we may copy the configuration from $c=c_1$ to $c=c_2$.

Lemma 1b: If there does not exist a configuration for $c=c_1$, then for any $c_2\ge{c_1}$, there does not exist a configuration for $c=c_2$. Note that any labeling which may be done for $c=c_2$ should also be available for $c=c_1$. However, we already stated that $c=c_1$ has no configuration, and so $c=c_2$ doesn't either.

We now prove that $c=\sqrt{2}$ does not work. WLOG, label the origin of our lattice plan with label $1$. WLOG, we can cover every point that we can with label $1$ because not labeling any such possible point does not affect the distance between points that aren't allowed to be labelled.

Name the state of the lattice grid before using label $1$ state $S$. After covering every point possible, we are left with only lattice points that have coordinates that sum to an odd integer. Notice, however, that if we discard the covered points and rotate all the new points by $\frac{\pi}{4}$ radians counterclockwise, we end up with the same grid as state $S$, only all the distances are multiplied by scalar $\sqrt{2}$. However, before placing label $2$s, note that we are in the same state $S$ as before, because our minimum distance is also multiplied by scalar $\sqrt{2}$. Thus, we will always be in an infinite loop, stuck in state $S$, and thus it is impossible to complete the labeling.

It suffices to show that any $c=2^{k}$ works given $k<0.5$. Note that the two smallest distances between any two points in the starting grid are $1$ and $\sqrt{2}$. When we are currently in state $S$ using label $I$, it is obvious that if $2ki-i\le{1}$, we can break out of state $S$ (Our effective minimum length would be at most 1, and we can cover every remaining point). Because $k<0.5$, there does exist an $I$ where this occurs. Thus, any $c<\sqrt{2}$ works, hence proved. $\blacksquare{}$ ~SigmaPiE

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