Задача 73693

Темы:    [ Доказательство от противного ] [ Обратный ход ] [ Принцип крайнего (прочее) ]

Сложность: 5 Классы: 7,8,9

Условие

Треугольная таблица строится по следующему правилу: в верхней её строке написано одно только натуральное число a > 1, а далее под каждым числом k слева пишем число k² , а справа — число k + 1. Докажите, что в каждой строке таблицы все числа разные.

Например, при a = 2 вторая строка состоит из чисел 4 и 3, третья — из чисел 16, 5, 9 и 4, четвёртая — из чисел 256, 17, 25, 6, 81, 10, 16 и 5.

Решение

Предположим, что в некоторых строчках таблицы встречаются одинаковые числа. Пусть 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+++ +... : сумма различных чисел, обратных натуральным, может быть сколь угодно большой.

Источники и прецеденты использования

журнал
Название	"Квант"
год
Год	1972
выпуск
Номер	8
Задача
Номер	М158