Problem 1770

1. Define the problem and notation:
For a positive integer $k \ge 2$, define $\mathcal{T}_k = \{(x, y) \mid x, y = 0, 1, \ldots, k-1\}$ to be a collection of $k^2$ lattice points on the Cartesian coordinate plane. Let $d_1(k) > d_2(k) > \cdots$ be the decreasing sequence of the distinct distances between any two points in $\mathcal{T}_k$. Suppose $S_i(k)$ is the number of distances equal to $d_i(k)$. We need to prove that for any three positive integers $m > n > i$, we have $S_i(m) = S_i(n)$.

2. Introduce the induction hypothesis:
Set $D_i(n) = d_i(n + 1)$, and associate with $D_i(n)$ a pair $(x_{n,i}, y_{n,i}) \in \{0, 1, \dots, n\}^2$ with $n \ge x_{n,i} \ge y_{n,i} \ge 0$ and $x_{n,i}^2 + y_{n,i}^2 = D_i(n)^2$. We will prove by induction on $n$ that for $1 \le i \le n$, the pairs $(x_i, y_i)$ are unique and equal, in order:
$$(n, n), (n, n - 1), (n, n - 2), (n - 1, n - 1), (n, n - 3), (n - 1, n - 2), \ldots$$

3. Base case:
When $n = 1$, the result is obvious because the only possible pairs are $(1, 1)$ and $(1, 0)$.

4. Induction step:
Suppose the hypothesis holds for $n = N - 1$. We need to show it holds for $n = N$. Notice that:
$$(x_{N, i}, y_{N, i}) = (x_{N - 1, i} + 1, y_{N - 1, i} + 1)$$
for $1 \le i \le N - 1$. This is because when $a^2 + b^2 > c^2 + d^2$ and $a + b \ge c + d$,
$$(a + 1)^2 + (b + 1)^2 = a^2 + b^2 + 2(a + b) + 1 > c^2 + d^2 + 2(c + d) + 1 = (c + 1)^2 + (d + 1)^2$$
and we know $y_i > 0$ and the sum $x_{N - 1, i} + y_{N - 1, i}$ is non-increasing in $i$.

5. Bijection and uniqueness:
There is a bijection from $D_i(N - 1)$ to $D_i(N)$ for $1 \le i \le N$, so the pairs $(x_{N, i}, y_{N, i})$ are unique and the hypothesis holds for $1 \le i \le N - 1$.

6. Final pair:
It remains to show that $(x_{N, N}, y_{N, N})$ obeys the hypothesis as well. Let $s = x_{N, N - 1} + y_{N, N - 1}$. If $x_{N, N - 1} - y_{N, N - 1} \le 1$, we have exhausted all possible values of $x_{N, i} + y_{N, i}$ greater than or equal to $s$, and so $x_{N, N} + y_{N, N} \le s - 1$. It follows that $x_{N, N} = n$ and $y_{N, N} = s - n - 1$ by the convexity of $f(t) = t^2$.

7. Explicit computation:
Otherwise, using the hypothesis, we can explicitly compute:
$$x_{N, N - 1} = N - (k - 1)$$
$$y_{N + 1, N} = N + 1 + (k - 1) - \lfloor \sqrt{4N + 2} \rfloor$$
where
$$k = N - 1 - \lfloor \frac{\lfloor \sqrt{4N + 2} \rfloor^2}{4} \rfloor$$

8. Convexity argument:
We claim $x_{N, N} = x_{N, N - 1} - 1$ and $y_{N, N} + y_{N, N - 1} + 1$. Again by the convexity of $f(t) = t^2$, it is sufficient to show:
$$(N - k)^2 + (N + 1 + k - \lfloor \sqrt{4N + 2} \rfloor)^2 > N^2 + (N - \lfloor \sqrt{4N + 2} \rfloor)^2$$
$$2k^2 - (2 \lfloor \sqrt{4N + 2} \rfloor - 2)k + (2N - 2 \lfloor \sqrt{4N + 2} \rfloor + 1) > 0$$
$$k = N - 1 - \lfloor \frac{\lfloor \sqrt{4N + 2} \rfloor^2}{4} \rfloor < \frac{2 \lfloor \sqrt{4N + 2} \rfloor - 2 - \sqrt{(2 \lfloor \sqrt{4N + 2} \rfloor - 2)^2 - 8(2N - 2 \lfloor \sqrt{4N + 2} \rfloor + 1)}}{4}$$

9. Simplification:
Now set $g = \lfloor \sqrt{4N + 2} \rfloor$. This can be rewritten:
$$N - 1 - \lfloor \frac{g^2}{4} \rfloor < \frac{g - 1 - \sqrt{(g + 1)^2 - (4N + 2)}}{2}$$
$$\sqrt{(g + 1)^2 - (4N + 2)} < 2 \lfloor \frac{g^2}{4} \rfloor + g + 1 - 2N$$
$$2 \sqrt{(g + 1)^2 - (4N + 2)} < 4 \lfloor \frac{g^2}{4} \rfloor + 2g + 4 - (4N + 2)$$

10. AM-GM inequality:
By AM-GM, it's sufficient to show:
$$1 + [(g + 1)^2 - (4N + 2)] < 4 \lfloor \frac{g^2}{4} \rfloor + 2g + 4 - (4N + 2)$$
$$g^2 < 4 \lfloor \frac{g^2}{4} \rfloor + 2$$
which follows from the fact that squares are either $0$ or $1$ modulo $4$.

Thus, we have shown that $S_i(m) = S_i(n)$ for all $m > n > i$.

$\blacksquare$