Задача 109692

Темы:    [ Рекуррентные соотношения (прочее) ] [ НОД и НОК. Взаимная простота ] [ Числа Фибоначчи ] [ Ограниченность, монотонность ] [ Монотонность и ограниченность ]

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

Условие

Автор: Волченков С.Г.

Найдите все бесконечные ограниченные последовательности натуральных чисел a₁, a₂, a₃, ..., для всех членов которых, начиная с третьего, выполнено

Решение

  Пусть  (a_k, a_k+1) = 1.  Тогда  (a_k, a_k+1) = (a_k + a_{k + 1}, a_k+1) = (a_k+2, a_k+1),  то есть для всех последующих членов последовательности НОД тоже будет равен 1. При этом, начиная с k-го члена, последовательность превращается в последовательность  a_n = a_n–1 + a_n–2,  которая неограниченно возрастает, что невозможно.
  Значит,  a_k+2 ≤ ½ max{a_k+1, a_k}  и  max{a_k+1, a_k}  не возрастает. Следовательно, когда-то он стабилизируется:
max{a_k+1, a_k} = max{a_k+2, a_k+1} = max{a_k+3, a_k+2} = ... = d.
  Если при этом  a_k+1 ≠ a_k,  то  a_k+2 < d,  a_k+3 < d,  что невозможно. Поэтому  a_k = a_k+1 = a_k+2 = ... = d,  откуда  d = 2.  Следовательно,     откуда  a_k–1 = 2,  и последовательность состоит только из двоек.

Ответ

a₁ = a₂ = ... = 2.

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

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