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

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

Условие

Для каждого натурального числа n обозначим через O(n) его наибольший нечётный делитель. Даны произвольные натуральные числа
х1 = а  и  х2 = b.  Построим бесконечную последовательность натуральных чисел по правилу:  xn = O(хn–1 + хn–2),  где  n = 3, 4, ... .
  а) Докажите, что, начиная с некоторого места, все числа в последовательности будут равны одному и тому же числу.
  б) Как найти это число, зная числа a и b?

Решение

  а) xn нечётно при  n > 2,  поэтому  xn+2 ≤ ½ (хn+1 + хn).  Следовательно, последовательность  yn = max {xn+1, xn}  не возрастает. Поскольку бесконечное убывание невозможно, эта последовательность стабилизируется:  ym = ym+1 = ym+2 = ...  Если  xmxm+1xm+2,  то  xm+2 < ymxm+3 < ym+1 = ym  и
ym+2 < ym  – противоречие. Значит,  xm+1 = xm+2 = xm+3 = ...

  б) Пусть  xm = xm+1 = xm+2 = ...  Обозначим  δ = O(НОД(a, b)).  Ясно, что все хn (в частности, xm) кратны δ. С другой стороны,  xm–1 = 2kxm+1xm  кратно xm, значит, xm–2 кратно xm. Продолжая, получим, что a и b кратны xm. Следовательно, δ кратно xm, то есть  δ = xm.


Ответ

б) Это  O(НОД(a, b)).

Замечания

баллы: 2 + 2

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

олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
задача
Номер 3

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

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