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

Проект МЦНМО
при участии
школы 57
Задача 109784
Темы:    [ Ограниченность, монотонность ]
[ Рекуррентные соотношения (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Рациональные и иррациональные числа ]
[ Целая и дробная части. Принцип Архимеда ]
[ Доказательство от противного ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Храбров А.

Последовательность натуральных чисел an строится следующим образом: a0 – некоторое натуральное число;  an+1 = ⅕ an,  если an делится на 5;
an+1 = [ an],  если an не делится на 5. Докажите, что начиная с некоторого члена последовательность an возрастает.


Решение

  Условие эквивалентно тому, что начиная с некоторого n число an не делится на 5. Докажем это.
  Покажем, что найдутся два соседних члена последовательности, не кратных 5. Предположим противное. Тогда для любого n либо an+1 получается из an делением на 5, либо an+2 получается из an+1 делением на 5. Заметим, что всегда  ak+1 ak ,  поэтому  an+2 ≤ ⅕ an < an.  Это означает, что последовательность натуральных чисел a1, a3, a5, ... строго убывает. Противоречие.
  Итак, найдутся ak и ak+1, не делящиеся на 5. Докажем, что ak+2 также не кратно 5. Так же последовательно получим, что ak+3, ak+4, ... не делятся на 5, что и требуется.
  ak+1 = [ ak],  ak+2 = [ ak+1].  Положим  ak = m,  тогда ak+1 = m – α,  где  0 < α < 1.  ak+2 = [( m – α] = 5m + [– α].  Но поскольку
0 < α < 3,  то  m – 3 ≤ ak+2 < 5m,  то есть ak+2 не делится на 5.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2003
Этап
Вариант 5
Класс
Класс 10
задача
Номер 03.5.10.6

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

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