Разделы 
Дополнительно
Задача по математике - 3614
2019-06-13 
В последовательности целых (положительных) чисел каждый член, начиная с третьего, равен модулю разности двух предыдущих.
Какое наибольшее число членов может иметь такая последовательность, если каждый ее член не превосходит 1967?
Решение:
Докажем, что длина (число членов) последовательности, удовлетворяющей условию задачи, у которой наибольший член - второй и равен $n$, не превосходит $d_n = \left [ \frac{3(n + 1)}{2} \right ]$, причем для последовательности $n - 1, n, 1, \cdots, 1, 1$ длина в точности равна $d_n$.
Будем рассуждать по индукции. Для $n \leq 4$ утверждение легко проверить перебором ($d_1 = 2, d_2 = 3, d_3 = 6, d_4 = 7$). Оценим максимальную длину последовательности с началом $a, n, n - a, \cdots (a < n)$, считая, что для меньших $n$ утверждение доказано. При $1 \leq a < n/2$ ее длина не больше $d_{n-a} + 1$, поскольку, убрав первый член $а$, можно заменить ее начало таким: $n - 2a, n - a, \cdots$; при $\frac{n}{2} \leq a < n - 1$ она не больше $d_a + 2$ - достаточно убрать первые два члена. Таким образом, остается лишь проверить, что для таких $a$ выполнены неравенства соответственно $d_{n-a} + 1 \leq d_n$ и $d_a + 2 \leq d_n$. При $a = n - 1$ - для последовательности $n - 1, n, 1, n - 1, n - 2, 1, n - 3, \cdots, 1, 1$ - достаточно убрать первые три члена и переставить два следующих, чтобы осталось лишь проверить равенство $d_{n-3} + 3 = d_n$.
Из общего утверждения при $n = 1967$ получаем ответ: $d_{1967} = \left [3 \cdot \frac{1968}{2} \right ] = 2952$.
Ответ: 2952.
В последовательности целых (положительных) чисел каждый член, начиная с третьего, равен модулю разности двух предыдущих.
Какое наибольшее число членов может иметь такая последовательность, если каждый ее член не превосходит 1967?
Решение:
Докажем, что длина (число членов) последовательности, удовлетворяющей условию задачи, у которой наибольший член - второй и равен $n$, не превосходит $d_n = \left [ \frac{3(n + 1)}{2} \right ]$, причем для последовательности $n - 1, n, 1, \cdots, 1, 1$ длина в точности равна $d_n$.
Будем рассуждать по индукции. Для $n \leq 4$ утверждение легко проверить перебором ($d_1 = 2, d_2 = 3, d_3 = 6, d_4 = 7$). Оценим максимальную длину последовательности с началом $a, n, n - a, \cdots (a < n)$, считая, что для меньших $n$ утверждение доказано. При $1 \leq a < n/2$ ее длина не больше $d_{n-a} + 1$, поскольку, убрав первый член $а$, можно заменить ее начало таким: $n - 2a, n - a, \cdots$; при $\frac{n}{2} \leq a < n - 1$ она не больше $d_a + 2$ - достаточно убрать первые два члена. Таким образом, остается лишь проверить, что для таких $a$ выполнены неравенства соответственно $d_{n-a} + 1 \leq d_n$ и $d_a + 2 \leq d_n$. При $a = n - 1$ - для последовательности $n - 1, n, 1, n - 1, n - 2, 1, n - 3, \cdots, 1, 1$ - достаточно убрать первые три члена и переставить два следующих, чтобы осталось лишь проверить равенство $d_{n-3} + 3 = d_n$.
Из общего утверждения при $n = 1967$ получаем ответ: $d_{1967} = \left [3 \cdot \frac{1968}{2} \right ] = 2952$.
Ответ: 2952.
