Задача 66624

Темы:    [ Задачи на проценты и отношения ] [ Последовательности ]

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

Условие

Автор: Френкин Б.Р.

Акции фирмы “Рога и копыта” каждый день меняют свою стоимость: поочерёдно то дорожают в $a$ раз, то дешевеют на $b$ рублей. Их стоимость уже трижды была равна $N$ рублей. Докажите, что рано или поздно она примет это значение и в четвёртый раз.

Решение

Первое решение. Пусть начальная стоимость акций составляет $c_0$ рублей, а после $i$-го дня она равна $c_i$ рублей ($i=1, 2, \ldots$).

Предположим, что $c_2>c_0$. Тогда $c_3=ac_2 > ac_0=c_1$ и $c_4=ac_2-b > ac_0-b=c_2$. Отсюда $c_1 < c_3 < c_5 < \dots$ и $c_0 < c_2 < c_4 < \dots$. Любое значение (в частности, $c$) появляется в каждой из двух цепочек не больше одного раза, поэтому всего не больше двух раз — противоречие с условием. Аналогично — если $c_2 < c_0$.

Значит, $c_2=c_0$, но тогда все значения с чётными индексами равны, так же как и все значения с нечётными индексами.

Второе решение. Аналогично первому решению введём последовательность цен акций. По условию, существует хотя бы три индекса $k$, $\ell$, $m$ такие, что $c_k=c_\ell=c_m=c$.

Из чисел $k$, $\ell$, $m$ хотя бы два одной чётности; пусть это $k$ и $\ell$, причём $k<\ell$. Осталось заметить, что тогда $c_{k+1}=c_{\ell+1}$ (в силу одинаковой чётности $k$ и $\ell$ для получения $c_{k+1}$ и $c_{\ell+1}$ мы с $c_k$ и $c_\ell$ проделываем одно и то же действие), $$c_{k+2}=c_{\ell+2}, \ldots, c_\ell=c_{2\ell-k}, \ldots, c_{2\ell-k}=c_{3\ell-2k},$$ откуда $c_{2\ell-k}=c_{3\ell-2k}=c$. Хотя бы одно из чисел $2\ell-k$ и $3\ell-k$ отлично от $m$, что завершает доказательство.

Замечания

Второе решение можно описать так: для получения $c_\ell$ из $c_k$ мы проделали какой-то набор действий. Но теперь мы из того же самого числа $(c_k=c_\ell=c)$ проделывается тот же самый набор действий (поскольку $k$ и $\ell$ одной чётности); поэтому мы опять получим то же самое число.

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

олимпиада
Название	Турнир им.Ломоносова
номер/год
Год	2018
задача
Номер	7