Задача 64516

Темы:    [ Рекуррентные соотношения (прочее) ] [ Четность и нечетность ] [ Делимость чисел. Общие свойства ]

Сложность: 4- Классы: 8,9,10

Условие

Автор: Гальперин Г.А.

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

Решение

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

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

Ответ

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

Замечания

баллы: 2 + 2

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

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