36-я Международная Математическая OлимпиадаКанада, Торонто, 1995 год

Найти наибольшее значение ${{x}_{0}}$, для которого существует последовательность положительных чисел ${{x}_{0}},{{x}_{1}},\ldots ,{{x}_{1995}}$, удовлетворяющая следующим условиям:
а) ${{x}_{0}}={{x}_{1995}}$;
б) ${{x}_{i-1}}+\dfrac{2}{{{x}_{i-1}}}=2{{x}_{i}}+\dfrac{1}{{{x}_{i}}}$ для всех $i=1,2,\ldots ,1995$.

Комментарий/решение

Ответ: $2^{997}$.

Данное рекуррентное соотношение является квадратным уравнением относительно $x_i$, корни которого $\frac{x_{i-1}}{2}, \frac{1}{x_{i-1}}$.

По методу математической индукции докажем, что $x_i$ имеет вид $2^kx_0^{\pm1}, k\in\mathbb{Z}, |k|\le i-1$.

База при $i=1$ очевидна.

Пусть это верно для $x_i=2^kx_0^{\pm1}$, тогда \[x_{i+1}=2^{k-1}x_0^{\pm1};\qquad|k-1|\le|k|+|-1|\le i\]

Либо \[x_i=2^{-k}x_0^{\mp1};\qquad|-k|\le i\]Таким образом переход доказан.

Рассмотрим полученный факт при $i=1995$

1) Если количество таких $i\le1994$, что $x_{i+1}=\frac1{x_i}$ нечётно, то

\[x_{1995}=2^kx_0^{-1}\Leftrightarrow x_0^2\le2^{1994}\Leftrightarrow x_0\le2^{997}\]

Пример для $x_0=2^{997}$: \[x_i=2^{997-i},(0\le i\le1994); x_{1995}=\frac{1}{x_{1994}}=x_0\]

2) В ином случае

\[x_0=x_{1995}= 2^kx_0\Leftrightarrow k=0\]

Отсюда, количество таких членов последовательности, $|k|$ которых на 1 больше, чем у предыдущего равно количеству таких членов последовательности, $|k|$ которых на 1 меньше предыдущего.

Т.е. количество таких $i$, что $x_{i+1}=\frac12x_i$ - чётно. Поэтому количество таких $i\le1994$, что $x_{i+1}=\frac1{x_i}$ нечётно. - противоречие