Предположим, что в некоторых строчках таблицы встречаются одинаковые числа, Пусть $n$ — номер самой верхней из этих строк, $p$ и $q$ — равные числа в строке с номером $n$. Так как в предыдущей строке равных чисел нет, то $p$ и $q$ получены из чисел предыдущей строки разными действиями: одно — возведением в квадрат, другое — добавлением 1. Пусть $p=r^2$, $q=s+1$, так что $s=r^2-1$. Числа $r$ и $s$ расположены в ($n-1$)-й строке. Рассмотрим путь, на котором из числа $a$ получилось число $s$. Предположим, что на этом пути встречались возведения в квадрат. Так как $s\lt r^2$, то самым большим числом, возводившимся в квадрат, могло быть $r-1$. Но $s-(r-1)^2=2r-2$. Это означает, что число $s$ из числа $(r-1)^2$ могло быть получено только добавлением единиц, причём для этого требовалось $2r-2$ шагов. Таким образом, число $s$ получилось из числа $a$ не менее чем за $2r-1$ шагов, так что $n-2\ge2r-1$. Но все числа, получающиеся из числа $a$ за такое число шагов, не меньше, чем $a+2r-1\gt r$, в то время как число $r$, расположенное в той же строке, что и $s$, получено из $a$ за то же число шагов, что и $s$. Таким образом, при получении числа $s$ из числа $a$ не было ни одного возведения в квадрат. Это же можно сказать и про число $q=s+1$. Следовательно, $q$ — наименьшее крайнее правое число в своей строчке, что противоречит равенству $q=p$.
Задаҹу можно обобщить следующим образом.
Пусть $f$ — функция, определённая на множестве натуральных чисел и принимающая натуральные значения. Предположим, что $f(n+1)-f(n)\gt n+1$ для каждого натурального числа $n$. Построим теперь треугольную таблицу по той же схеме, что и в задаче, но применяя каждый раз функцию $f$ вместо возведения в квадрат:
$$
\def\l{\mathrlap\diagup}
\def\r{\mathllap\diagdown}
\def\L{\mathrlap/}
\def\R{\mathllap\backslash}
\def\.{\mathclap\cdot}
\def\f{\hskip2.5em}
\def\e{\hskip3em}
\def\d{\hskip1.75em}
\def\c{\hskip2em}
\def\b{\hskip1em}
\def\a{\hskip1em}
\begin{array}{c}
2\\
\l\f\r\\
\mathclap{f(2)}\e\mathclap3\\
\l\d\R\d~\L\d\r\\
\mathclap{f(f(2))~~~~~~~~~}\c\mathclap{f(2){+}1}\c\mathclap{~~~~~f(3)}\c\mathclap4\\
\L\b\R\b\L\b\R\b\L\b\R\b\L\b\R\\
\.\a\.\a\.\a\.\a\.\a\.\a\.\a\.\\
\end{array}
$$
Тогда в каждой строке таблицы все числа различны.
Приведём одно интересное следствие задачи М158.
Пусть бесконечная последовательность положительных чисел $a_1$, $a_2$, $a_3$, $\ldots$ такова, что для каждого натурального числа $n$
$$
a_n\lt a_{n+1}+a_{n^2},\tag{*}
$$
так что $a_3\lt a_3+a_4$, $a_3\lt a_4+a_9$, $a_4\lt a_5+a_{18}$ и т. д. Тогда из этих чисел можно выбрать несколько, сумма которых больше 1000. Число 1000 здесь можно заменить любым другим числом. (Как говорят, ряд $a_1+a_2+a_3+\ldots+a_n+\ldots$ расходится.)
Условию (*) удовлетворяет, в частности, последовательность $a_n=\dfrac1n$, так что из этого следствия можно получить ещё одно доказательство знаменитой теоремы о расходимости гармонического ряда $1+\dfrac12+\dfrac13+\dfrac14+\ldots$: сумма различных чисел, обратных натуральным, может быть сколь угодно большой.
