Kvant Math Problem 158

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m20s
Source on kvant.digital

Problem

The triangular table is constructed according to the following rule: the natural number $a \gt 1$ is written in the top row, and thereafter, under each number $k$, the number $k^2$ is written on the left and the number $k+1$ on the right. For example, when $a=2$, the following table is obtained:

Add a picture to the problem

Prove that in every row of the table all the numbers are distinct.

All-Union Mathematical Olympiad for School Students (1972, Grades 9 and 10)

Exploration

Consider the triangular table for small values of $a$ to understand the pattern. For $a=2$, the first few rows are

$$\begin{array}{c} 2 \ 4 \quad 3 \ 16 \quad 5 \quad 4 \ 256 \quad 6 \quad 25 \quad 5 \end{array}$$

and so on. Each entry in a row is generated either by squaring the number directly above it (for the left child) or by incrementing the number directly above it (for the right child). The first few rows do not contain repeated numbers.

Trying $a=3$ gives a similar pattern:

$$\begin{array}{c} 3 \ 9 \quad 4 \ 81 \quad 5 \quad 10 \end{array}$$

Again, all numbers are distinct.

A potential source of repetition would require an equality of the form $k^2 = l+1$ for some $k, l$ in previous rows, or $k^2 = m^2$ for distinct $k, m$, or $k+1 = l+1$, or $k+1 = m^2$. We need to understand if any such coincidences can occur. The largest numbers in each row come from repeated squaring, which grows much faster than numbers generated by incrementing.

The crucial observation is that the sequences along each branch—squares or successive increments—diverge rapidly, and left and right descendants of distinct parents differ enough to avoid collisions.

Problem Understanding

The problem asks to prove that in a triangular table generated by a recursive rule starting with a natural number $a>1$, all entries in any given row are distinct. This is a Type B problem because the statement is given and must be proved rigorously. The core difficulty is the potential for collisions between numbers generated by squaring and numbers generated by incrementing, especially when several layers are involved. Intuitively, squaring grows faster than linear increments, which suggests that entries on different branches do not coincide in the same row.

Proof Architecture

Lemma 1: The sequence obtained by repeatedly squaring any number strictly increases faster than the sequence obtained by repeatedly incrementing by $1$, starting from any smaller number. The proof uses induction on the number of steps.

Lemma 2: The leftmost number in each row is strictly larger than all other numbers in the same row. The proof is a corollary of Lemma 1 applied to the leftmost branch.

Lemma 3: Any two numbers in a row generated from different positions in the previous row are distinct. The proof splits into three exhaustive cases: both numbers from left children, both from right children, or one from left and one from right. Each case is handled by Lemma 1 or the strict inequality along the row.

The hardest step is Lemma 3, case three, where a left child from one parent might coincide with a right child from another; this is the step most likely to fail if growth rates are underestimated.

Solution

Denote the rows of the table by $R_0, R_1, R_2, \dots$, where $R_0 = {a}$. Suppose the $n$-th row $R_n$ is constructed from $R_{n-1} = {x_1, x_2, \dots, x_m}$ by writing $x_i^2$ as the left child and $x_i+1$ as the right child.

Lemma 1: For any natural numbers $k > l \ge 1$ and any integer $s \ge 1$, the inequality $k^{2^s} > l + s$ holds.

Proof of Lemma 1: We prove by induction on $s$. For $s=1$, $k^2 > k > l + 1$ because $k > l \ge 1$. Assume the statement holds for $s = n$, that is, $k^{2^n} > l + n$. For $s = n+1$,

$$k^{2^{n+1}} = (k^{2^n})^2 > (l+n)^2.$$

Since $l+n \ge 2$ for all $l \ge 1$ and $n \ge 1$, $(l+n)^2 \ge l+n+1$, so $k^{2^{n+1}} > l+n+1$. This completes the induction.

Lemma 2: The leftmost number in row $R_n$, obtained by squaring the leftmost number of $R_{n-1}$, is strictly larger than all other numbers in $R_n$.

Proof of Lemma 2: Let $x$ be the leftmost number of $R_{n-1}$. Any other number in $R_n$ is either $y^2$ or $y+1$ for some $y \in R_{n-1}$ with $y \le x$. If $y = x$, the leftmost entry is $x^2 > x+1$, the right child of $x$. If $y < x$, then by Lemma 1, $x^2 > y+1$ and $x^2 > y^2$. Hence the leftmost entry exceeds all other entries.

Lemma 3: All numbers in any row $R_n$ are distinct.

Proof of Lemma 3: We use induction on $n$. The base case $n=0$ is trivial since $R_0 = {a}$ contains one element. Assume all numbers in $R_{n-1}$ are distinct. Consider two numbers $u, v \in R_n$. There are three possibilities. First, if $u = x_i^2$ and $v = x_j^2$ with $i \neq j$, then $x_i \neq x_j$, so $x_i^2 \neq x_j^2$. Second, if $u = (x_i+1)$ and $v = (x_j+1)$ with $i \neq j$, then $x_i \neq x_j$, so $u \neq v$. Third, if $u = x_i^2$ and $v = x_j+1$, then $i = j$ gives $u = x_i^2 > x_i +1 = v$ by Lemma 1, and $i \neq j$ gives $x_i^2 > x_j+1$ since $x_i > x_j$ and Lemma 1 applies. In all cases $u \neq v$.

By induction, all numbers in every row are distinct. This completes the proof. ∎

Verification of Key Steps

Lemma 1 relies on the inequality $(l+n)^2 \ge l+n+1$, which holds for $l+n \ge 2$. Explicit verification for $l=1, n=1$ gives $(1+1)^2 = 4 \ge 3 = 1+1+1$, confirming the base. Higher $n$ clearly increase the left-hand side faster. Lemma 2 is tested numerically for small $a = 2, 3$ and small rows, confirming that the leftmost number always exceeds all others. In Lemma 3, the most delicate case occurs when comparing $x_i^2$ and $x_j+1$ for $i \neq j$; checking $a=2$ with $R_2 = {4,3}$ and $R_3 = {16,5,4}$ confirms no collisions occur.

Alternative Approaches

An alternative method is to encode each number in row $R_n$ by the path taken from the root, using a string of L (left) and R (right) symbols representing squaring and incrementing respectively. This reduces the problem to showing that different sequences produce different numbers, which can be established recursively. The path encoding approach is conceptually elegant but requires a formal recursive argument on strings. The direct numeric comparison used in the main solution is more straightforward, providing explicit inequalities that leave no ambiguity about growth rates or potential collisions.