ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73693
Темы:    [ Доказательство от противного ]
[ Обратный ход ]
[ Принцип крайнего (прочее) ]
Сложность: 5
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

Треугольная таблица строится по следующему правилу: в верхней её строке написано одно только натуральное число a > 1, а далее под каждым числом k слева пишем число k2 , а справа — число 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=r2 , q=s+1 , так что s=r2-1 . Числа r и s расположены в (n-1) -й строке. Рассмотрим путь, на котором из числа a получилось число s . Предположим, что на этом пути встречались возведения в квадрат. Так как s<r2 , то самым большим числом, возводившимся в квадрат могло быть r-1 . Но s-(r-1)2=2r-2 . Это означает, что число s из числа (r-1)2 могло быть получено только добавлением единиц, причем для этого требовалось 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.

Пусть бесконечная последовательность положительных чисел a1 , a2 , a3, ... такова, что для каждого натурального числа n

an<an+1+an2,

так что a2<a3+a4 , a3<a4+a9 , a4<a5+a16 и т.д. Тогда из этих чисел можно выбрать несколько, сумма которых больше 1000 . Число 1000 здесь можно заменить любым другим числом. (Как говорят, ряд a1+a2+ a3+...+an+... расходится.)

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

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .