Maths Olympiad Prep

Library / /81 of 115

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine all real numbers c>0 c > 0 such that there exists a labeling of the lattice points (x,y)Z2 (x, y) \in \mathbf{Z}^2 with positive integers while satisfying the given conditions:
- Only finitely many distinct labels occur.
- For each label i i , the distance between any two points labeled i i is at least ci c^i .

Given the reference answer, we are looking for c c such that c<2 c < \sqrt{2} . Let's see why this holds:

1. Understanding Distances in the Lattice:
Consider the Euclidean distance between two lattice points (x1,y1) (x_1, y_1) and (x2,y2) (x_2, y_2) in Z2 \mathbf{Z}^2 . This distance is given by:
d((x1,y1),(x2,y2))=(x2x1)2+(y2y1)2. d((x_1, y_1), (x_2, y_2)) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.

2. Labeling with Condition on Distances:
For a fixed label i i , the distance between any two points with this label must be ci \geq c^i . We need infinitely many points since the lattice Z2 \mathbf{Z}^2 is infinite, but only finitely many distinct labels. Thus, the labeling for each label i i inherently restricts possible distances between pairs of points.

3. **Bounding c c :**
- If c2 c \geq \sqrt{2} , consider any two adjacent lattice points, say (x,y) (x, y) and (x+1,y) (x+1, y) or (x,y+1) (x, y+1) . For sufficiently large i i , ci c^i will exceed any possible finite maximum distance between these pairs using distinct labels, contradicting the need for only finitely many labels.
- If c<2 c < \sqrt{2} , then for any integer i i , ci c^i can be smaller than the shortest distance (2)(\sqrt{2}) between two adjacent lattice points. Therefore, it becomes possible to find suitable points and repeatedly assign the same labels within these constraints.

4. Conclusion:
The condition c<2 c < \sqrt{2} ensures that the labeling can satisfy both criteria provided: controlling the finite number of labels and maintaining the required distances between points with the same label.

Thus, the values of c c that satisfy the problem's conditions are indeed:
c<2 \boxed{c < \sqrt{2}}
This completes the correctness validation of the initial reference answer by logically confirming the constraints outlined in the labeling problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.