Problem:
Let 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)∈Z2 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 ci.
Solution:
(Proposed by Ricky Liu)
The answer is c<2​.
First suppose c<2​. We can partition Z2 into two subsets
L1​={(x,y)∣x+y is odd } and L1′​={(x,y)∣x+y is even }
Both L1​ and L1′​ are square lattices with unit length 2​ (that is, they are similar to Z2 with a scaling factor of 2​ ). Hence we can similarly partition L1′​ into two square lattices L2​ and L2′​ with unit length 2​2, then partition L2′​ into two square lattices L3​ and L3′​ with unit length 2​3, and so forth. Hence for any N≥1,Z2 can be partitioned into N+1 square lattices L1​,L2​,…,LN​,LN′​ with unit lengths 2​,2​2,…,2​N,2​N, respectively.
Since c2​​>1, there exists a positive integer N such that (c2​​)N+1≥2​, or equivalently, cN+1≤2​N. For i=1,…,N, label all points in Li​ by i, and then label all points in LN′​ by N+1. Any two points in Li​ lie at least 2​i>ci apart, while any two points in LN′​ lie at least 2​N≥cN+1 apart, so this is a valid labeling.
Suppose instead that c≥2​. For a nonnegative integer m, define
Rm​={(x,y)∣1≤x≤2a,1≤y≤2b}⊆Z2, where (a,b)={(2m​,2m​)(2m−1​,2m+1​)​ if m is even if m is odd ​
We will show by induction that Rm​ does not have a valid labeling using only labels at most m, which will prove that Z2 has no valid labeling. The case m=0 is trivial.
Suppose m>0 is odd and that Rm−1​ does not have a valid labeling using only 1,…,m−1 (the inductive hypothesis), but that Rm​ does have a valid labeling using only 1,…,m. Consider this labeling of Rm​. Since Rm​⊇Rm−1​, some point (x0​,y0​) with y0​≤2(m−1)/2 must be labeled m. But then (x0​,y0​) lies directly below a translate R′ of Rm−1​ inside Rm​. The distance between (x0​,y0​) and any point in R′ is at most
(22m−1​−1)2+(22m−1​)2​<2​m≤cm
so no points in R′ can be labeled m. But by the inductive hypothesis, R′ has no valid labeling using only 1,…,m−1, which is a contradiction.
Now suppose m>0 is even and that Rm−1​ does not have a valid labeling using only 1,…,m− 1 (the inductive hypothesis), but Rm​ does have a valid labeling using only 1,…,m. By the inductive hypothesis, some point (x0​,y0​) with 41​⋅2m/2<y0​≤43​⋅2m/2 must be labeled m (since the corresponding rows of Rm​ form a rotated copy of Rm−1​ ). But then ( x0​,y0​) lies either directly to the left or to the right of a translate R′ of Rm−1​ inside Rm​. The distance between (x0​,y0​) and any point of R′ is less than
so no points in R′ can be labeled m. But by the inductive hypothesis, R′ has no valid labeling using only 1,…,m−1, which is a contradiction. This completes the proof.