Предположим, что в некоторых строчках таблицы встречаются одинаковые числа. Пусть n – номер самой верхней из этих строк, p и q – равные числа в строке с номером n . Так как в предыдущей строке равных чисел нет, то p и q получены из чисел предыдущей строки разными действиями: одно– возведением в квадрат, другое– добавлением1. Пусть p=r² , q=s+1, так что s=r²-1. Числа r и s расположены в(n-1)-й строке. Рассмотрим путь, на котором из числа a получилось число s . Предположим, что на этом пути встречались возведения в квадрат. Так как s<r² , то самым большим числом, возводившимся в квадрат могло быть r-1. Но s-(r-1)²=2r-2. Это означает, что число s из числа(r-1)² могло быть получено только добавлением единиц, причем для этого требовалось2r-2шага. Таким образом, число s получилось из числа a не менее чем за2r-1шагов, так что n-2 2r-1. Но все числа, получающиеся из числа a за такое число шагов, не меньше, чем a+2r-1>r , в то время как число r , расположенное в той же строке, что и s , получено из a за то же число шагов, что и s . Таким образом, при получении числа s из числа a не было ни одного возведения в квадрат. Это же можно сказать и про число q=s+1. Следовательно, q – наименьшее крайнее правое число в своей строчке, что противоречит равенству q=p .

Задачу можно обобщить следующим образом.

Пусть f – функция, определенная на множестве натуральных чисел и принимающая натуральные значения. Предположим, что f(n+1)-f(n)>n+1 для каждого натурального числа n . Построим теперь треугольную таблицу по той же схеме, что и в задаче, но применяя каждый раз функцию f вместо возведения в квадрат:

Тогда в каждой строке таблицы все числа различны.

Приведем одно интересное следствие задачи M158.

Пусть бесконечная последовательность положительных чисел a₁ , a₂ , a₃, ... такова, что для каждого натурального числа n

a_n<a_n+1+a_n²,

так что a₂<a₃+a₄ , a₃<a₄+a₉ , a₄<a₅+a16и т.д. Тогда из этих чисел можно выбрать несколько, сумма которых больше1000. Число1000здесь можно заменить любым другим числом. (Как говорят, ряд a₁+a₂+ a₃+...+a_n+... расходится.)

Условию (*) удовлетворяет, в частности, последовательность a_n=1/n , так что из этого следствия можно получить еще одно доказательство знаменитой теоремы о расходимости гармонического ряда 1+++ +... : сумма различных чисел, обратных натуральным, может быть сколь угодно большой.

Ответ задачи отсутствует