Problem 1119

163. Suppose that in some rows of the table, the same numbers appear. Let $n$ be the number of the highest such row, and $p$ and $q$ be the equal numbers in this row.

Since there are no equal numbers in the $(n-1)$-th row, $p$ and $q$ are obtained from numbers $r$ and $s$ in this row through different operations: let $p=r^2, q=s+1$, then $s=r^2-1$.

On the path leading from the top number $a$ to the number $s$, there could have been squaring and adding of ones. The largest number that could have been squared was $r-1$ (since $s=r^2-1$). This means that the number $s$ could have been obtained from the last square encountered on the path in no fewer than $r^2-1-(r-1)^2=2r-2$ steps, with one being added at each step. Thus, the number $s$ was obtained from $a$ in no fewer than $2r-1$ steps (i.e., $n-2 \geq 2r-1$). But in the same row as $s$ stands $r$, and any number obtained from $a$ in such a number of steps is no less than $a+2r-1 > r$. Therefore, there were no squaring operations in obtaining $s$, so $q$ is the rightmost, smallest number in the $n$-th row, which contradicts the equality $p=q$.

$\nabla$ The analysis of the solution shows that the squaring operation can be replaced by any function $f$ that takes natural values and such that $f(n+1) - f(n) > n+1$.

!

Fig. 67