Разделы 
Дополнительно
Задача по математике - 2903
2019-05-06 
Последовательность натуральных чисел $a_0, a_1, a_2, a_3, \cdots$ составляется по следующему правилу:
$a_0, a_1, a_2 = |a_0 - a_1|, a_3 = |a_1 - a_2|, \cdots$
(и вообще $a_n = |a_{n-2} - a_{n-1}|$ при всех продолжается последовательность до первого нуля. Известно, что каждое входящее в последовательность число не превосходит 1967. Какое наибольшее количество чисел может содержать такая последовательность?
Решение:
Нетрудно понять, что наибольшим числом нашей последовательности может быть лишь одно из первых двух чисел $a_0$ и $a_1$ (ибо каждое $a_k$ при $k \geq 2$ обязательно $< max [a_{k-1}, a_{k-2}]$. Легко даже видеть, что в наибольшей по длине последовательности самым большим является именно число $a_1$ ибо если последовательность начинается с чисел $a_1, a_2, a_3, \cdots$, где $a_1 > a_2$, то ее можно, не меняя, «продолжить назад», условившись начинать так: $a_0 = a_1 - a_2, a_1, a_2 = |a_1 - a_0|, a_3, \cdots$ (здесь, очевидно, $a_1 > a_0 = a_1 - a_2$). Поэтому в дальнейшем мы ограничимся лишь рассмотрением последовательностей, начинающихся с наибольшего числа $a_1 > a_0 = a_1 - a_2$; (нам только при этом придется в окончательном ответе увеличить длину последовательности на 1 за счет «нулевого» по номеру числа $a_0 = a_1 - a_2$).
Ясно, что если наибольший член последовательности $a_1 = 1$, то последовательность состоит не более чем из двух чисел (продолжить ее можно лишь одним числом $a_2 = 1$); если наибольший член последовательности $a_1 = 2$, то количество входящих в последовательность чисел $\leq 3$ (если $a_2 = 2$, то последовательность имеет вид: 2, 2, а если $a_2 = 1$, то она такова: 2, 1, 1); если $a_1 = 3$, то число входящих в последовательность чисел $\leq 5$ (полагая, что $a_2 = 3, 2 \: или 1$, мы приходим к последовательностям: $3, 3$; или $3, 2, 1$; или, наконец, $3, 1, 2, 1, 1$). Эти примеры подсказывают заключение о том, что «оптимальная» последовательность, по-видимому, должна начинаться с чисел $a_1 = n$, $a_2 = 1$. При этом начало ее выглядит так:
$n, 1, n-1, n-2, 1, \cdots$ (*)
откуда вытекает, что, обозначив количество чисел, составляющих последовательность (*), через $k_n$, мы получим:
$k_n = 3 + k_{n-2}$ (**)
(ведь, начиная с 4-го члена $a_4 = n-2$, мы приходим к подобной же последовательности, где $n$ заменено на $n-2$).
Из соотношения (**) находим:
$k_1 = 2, k_2 = 3, k_3 = 3 + 2 = 5, k_4 = 3 + 3 = 6, k_5 = 3 + 5 = 8, k_6 = 3 + 6 = 9, \cdots$,
все эти числа $k_n$ задаются следующей формулой:
$k_n = \left [ \frac{3n+1}{2} \right ]$, (***)
где квадратные скобки, как всегда, обозначают целую часть числа. (Формулу (***), разумеется, совсем просто вывести из (**) с помощью метода математической индукции: для $n = 1$ и $n = 2$ она, как мы видели, справедлива; если (***) верно для значения $n - 2$, то для значения $n$ это соотношение тоже верно:
$k_n = k_{n-2} + 3 = \left [ \frac {3(n-2) + 1}{2} \right ] + 3 = \left [ \frac{3n+1}{2} \right ]$.
Итак, мы уже построили (начинающуюся с наибольшего числа!) последовательность (*), длина $k_n$ которой связана с величиной $n$ наибольшего числа соотношением (***); покажем теперь, что если описанная в условии задачи последовательность, начинается с наибольшего числа $a_1 = n$, то длина ее не может превзойти указываемого формулой (***) числа $k_n$. Доказывать это мы будем, естественно, по индукции: предположим, что напечатанное курсивом утверждение уже доказано для всех значений $n$, меньших некоторого (а справедливость его для значений $n = 1, 2$ и 3 мы уже проверили), и покажем, что тогда оно будет справедливо и для значения $n$. В самом деле, пусть задана удовлетворяющая условиям задачи последовательность, начинающаяся числами:
$n, m, \cdots$,
где $, \leq n$. Далее рассмотрим ряд вариантов, отвечающих разным значениям $m$.
1°. Если $m = n$, то последовательность обрывается на 2-м члене; для нее наше утверждение, конечно, выполнено.
2°. Если $n$ - четное число и $m = \frac{n}{2}$, то последовательность обрывается обрывается на 3-м члене: $n, \frac{n}{2}, \frac{n}{2}$, и здесь тоже, разумеется, длина последовательности меньше $k_n$.
3°. Если $n > m > \frac{n}{2}$, то, отбросив в нашей последовательности первое число $n$, мы получим «в остатке» последовательность $m$, $n-m, \cdots$, тоже начинающуюся с большего числа $m$; по предположению индукции, этот «остаток» содержит не более $k_m = \left [ \frac{3m+1}{2} \right ]$ чисел. Но так как одно число мы при этом отбросили и так как $m \leq n - 1$, то вся последовательность содержит не более чем
$1 + \left [ \frac{3m+1}{2} \right ] \leq 1 + \left [ \frac{3(n-1) + 1}{2} \right ] = \left [ \frac{3n}{2} \right ] \leq \left [ \frac{3n+1}{2} \right ] = k_n$
чисел.
4°. Если, наконец, $m < \frac{n}{2}$, то наша последовательность начинается так: $n, m, n-m, n-2m, m, \cdots$. При этом если $n - 2m \geq m$ (т. е. $m \leq \frac{n}{3}$), то «остаток» последовательности, получающийся после отбрасывания первых трех чисел (остаток, начинающийся с числа $n-2m$), таков, что наибольшим в этой последовательности чисел является первое ее число; поэтому, по предположению индукции, количество содержащихся в остатке чисел не превосходит
$k_{n-2m} = \left [ \frac {3(n-2m)+1}{2} \right ] \leq \left [ \frac {3(n-2) + 1}{2} \right ] = \left [ \frac{3n+1}{2} \right ] - 3$,
(ибо $m \geq 1$) и, значит, общее число чисел не превосходит $\left [ \frac{3n+1}{2} \right ] = k_n$.
Если же $n - 2m$ (т. е. $m > \frac{n}{3}$), то поскольку здесь шестое число последовательности $m - (n - 2m) < m$, то начинающийся с пятого числа $m$ «остаток» будет таков, что в нем наибольшее число $m$ стоит на первом месте; поэтому число чисел «остатка» $\leq k_m = \left [ \frac{3m+1}{2} \right ] \leq \left [ \frac{3m+2}{4} \right ]$ – и снова общее количество входящих в последовательность чисел $\leq k_m + 4 \leq \left [ \frac{3n+2}{4} \right ] + 4 \leq \left [ \frac{3n+1}{2} \right ] = k_n$.
Тем самым мы полностью доказали утверждение, относящееся к последовательностям, начинающимся с наибольшего числа. А отсюда следует, что заданная в условии задачи последовательность не может содержать больше чем $1 + k_{1967} = 1 + \left [ \frac{3 \cdot 1967 + 1}{2} \right ] = 2952$ числа; количество входящих в последовательность чисел равно 2952 в том и только в том случае, если она начинается с чисел: $1966, 1967, 1, 1966, 1965, 1, 1964, 1963, 1, \cdots$.
Последовательность натуральных чисел $a_0, a_1, a_2, a_3, \cdots$ составляется по следующему правилу:
$a_0, a_1, a_2 = |a_0 - a_1|, a_3 = |a_1 - a_2|, \cdots$
(и вообще $a_n = |a_{n-2} - a_{n-1}|$ при всех продолжается последовательность до первого нуля. Известно, что каждое входящее в последовательность число не превосходит 1967. Какое наибольшее количество чисел может содержать такая последовательность?
Решение:
Нетрудно понять, что наибольшим числом нашей последовательности может быть лишь одно из первых двух чисел $a_0$ и $a_1$ (ибо каждое $a_k$ при $k \geq 2$ обязательно $< max [a_{k-1}, a_{k-2}]$. Легко даже видеть, что в наибольшей по длине последовательности самым большим является именно число $a_1$ ибо если последовательность начинается с чисел $a_1, a_2, a_3, \cdots$, где $a_1 > a_2$, то ее можно, не меняя, «продолжить назад», условившись начинать так: $a_0 = a_1 - a_2, a_1, a_2 = |a_1 - a_0|, a_3, \cdots$ (здесь, очевидно, $a_1 > a_0 = a_1 - a_2$). Поэтому в дальнейшем мы ограничимся лишь рассмотрением последовательностей, начинающихся с наибольшего числа $a_1 > a_0 = a_1 - a_2$; (нам только при этом придется в окончательном ответе увеличить длину последовательности на 1 за счет «нулевого» по номеру числа $a_0 = a_1 - a_2$).
Ясно, что если наибольший член последовательности $a_1 = 1$, то последовательность состоит не более чем из двух чисел (продолжить ее можно лишь одним числом $a_2 = 1$); если наибольший член последовательности $a_1 = 2$, то количество входящих в последовательность чисел $\leq 3$ (если $a_2 = 2$, то последовательность имеет вид: 2, 2, а если $a_2 = 1$, то она такова: 2, 1, 1); если $a_1 = 3$, то число входящих в последовательность чисел $\leq 5$ (полагая, что $a_2 = 3, 2 \: или 1$, мы приходим к последовательностям: $3, 3$; или $3, 2, 1$; или, наконец, $3, 1, 2, 1, 1$). Эти примеры подсказывают заключение о том, что «оптимальная» последовательность, по-видимому, должна начинаться с чисел $a_1 = n$, $a_2 = 1$. При этом начало ее выглядит так:
$n, 1, n-1, n-2, 1, \cdots$ (*)
откуда вытекает, что, обозначив количество чисел, составляющих последовательность (*), через $k_n$, мы получим:
$k_n = 3 + k_{n-2}$ (**)
(ведь, начиная с 4-го члена $a_4 = n-2$, мы приходим к подобной же последовательности, где $n$ заменено на $n-2$).
Из соотношения (**) находим:
$k_1 = 2, k_2 = 3, k_3 = 3 + 2 = 5, k_4 = 3 + 3 = 6, k_5 = 3 + 5 = 8, k_6 = 3 + 6 = 9, \cdots$,
все эти числа $k_n$ задаются следующей формулой:
$k_n = \left [ \frac{3n+1}{2} \right ]$, (***)
где квадратные скобки, как всегда, обозначают целую часть числа. (Формулу (***), разумеется, совсем просто вывести из (**) с помощью метода математической индукции: для $n = 1$ и $n = 2$ она, как мы видели, справедлива; если (***) верно для значения $n - 2$, то для значения $n$ это соотношение тоже верно:
$k_n = k_{n-2} + 3 = \left [ \frac {3(n-2) + 1}{2} \right ] + 3 = \left [ \frac{3n+1}{2} \right ]$.
Итак, мы уже построили (начинающуюся с наибольшего числа!) последовательность (*), длина $k_n$ которой связана с величиной $n$ наибольшего числа соотношением (***); покажем теперь, что если описанная в условии задачи последовательность, начинается с наибольшего числа $a_1 = n$, то длина ее не может превзойти указываемого формулой (***) числа $k_n$. Доказывать это мы будем, естественно, по индукции: предположим, что напечатанное курсивом утверждение уже доказано для всех значений $n$, меньших некоторого (а справедливость его для значений $n = 1, 2$ и 3 мы уже проверили), и покажем, что тогда оно будет справедливо и для значения $n$. В самом деле, пусть задана удовлетворяющая условиям задачи последовательность, начинающаяся числами:
$n, m, \cdots$,
где $, \leq n$. Далее рассмотрим ряд вариантов, отвечающих разным значениям $m$.
1°. Если $m = n$, то последовательность обрывается на 2-м члене; для нее наше утверждение, конечно, выполнено.
2°. Если $n$ - четное число и $m = \frac{n}{2}$, то последовательность обрывается обрывается на 3-м члене: $n, \frac{n}{2}, \frac{n}{2}$, и здесь тоже, разумеется, длина последовательности меньше $k_n$.
3°. Если $n > m > \frac{n}{2}$, то, отбросив в нашей последовательности первое число $n$, мы получим «в остатке» последовательность $m$, $n-m, \cdots$, тоже начинающуюся с большего числа $m$; по предположению индукции, этот «остаток» содержит не более $k_m = \left [ \frac{3m+1}{2} \right ]$ чисел. Но так как одно число мы при этом отбросили и так как $m \leq n - 1$, то вся последовательность содержит не более чем
$1 + \left [ \frac{3m+1}{2} \right ] \leq 1 + \left [ \frac{3(n-1) + 1}{2} \right ] = \left [ \frac{3n}{2} \right ] \leq \left [ \frac{3n+1}{2} \right ] = k_n$
чисел.
4°. Если, наконец, $m < \frac{n}{2}$, то наша последовательность начинается так: $n, m, n-m, n-2m, m, \cdots$. При этом если $n - 2m \geq m$ (т. е. $m \leq \frac{n}{3}$), то «остаток» последовательности, получающийся после отбрасывания первых трех чисел (остаток, начинающийся с числа $n-2m$), таков, что наибольшим в этой последовательности чисел является первое ее число; поэтому, по предположению индукции, количество содержащихся в остатке чисел не превосходит
$k_{n-2m} = \left [ \frac {3(n-2m)+1}{2} \right ] \leq \left [ \frac {3(n-2) + 1}{2} \right ] = \left [ \frac{3n+1}{2} \right ] - 3$,
(ибо $m \geq 1$) и, значит, общее число чисел не превосходит $\left [ \frac{3n+1}{2} \right ] = k_n$.
Если же $n - 2m$ (т. е. $m > \frac{n}{3}$), то поскольку здесь шестое число последовательности $m - (n - 2m) < m$, то начинающийся с пятого числа $m$ «остаток» будет таков, что в нем наибольшее число $m$ стоит на первом месте; поэтому число чисел «остатка» $\leq k_m = \left [ \frac{3m+1}{2} \right ] \leq \left [ \frac{3m+2}{4} \right ]$ – и снова общее количество входящих в последовательность чисел $\leq k_m + 4 \leq \left [ \frac{3n+2}{4} \right ] + 4 \leq \left [ \frac{3n+1}{2} \right ] = k_n$.
Тем самым мы полностью доказали утверждение, относящееся к последовательностям, начинающимся с наибольшего числа. А отсюда следует, что заданная в условии задачи последовательность не может содержать больше чем $1 + k_{1967} = 1 + \left [ \frac{3 \cdot 1967 + 1}{2} \right ] = 2952$ числа; количество входящих в последовательность чисел равно 2952 в том и только в том случае, если она начинается с чисел: $1966, 1967, 1, 1966, 1965, 1, 1964, 1963, 1, \cdots$.
