Задача
Дана последовательность целых положительных чиселX1,X2...Xn, все элементы которой не превосходят некоторого числаM. Известно, что при всехk> 2Xk= |Xk - 1-Xk - 2|. Какой может быть максимальная длина этой последовательности?
Решение
Обозначим через $\lceil$x$\rceil$наименьшее целое число, не меньшее x, а через $\lfloor$x$\rfloor$ — наибольшее целое число, не превосходящее x.
Докажем, что наибольшая длина L(M) такой последовательности равна
\end{equation*} -->
| L(M) = $M=1$ |
Найдём сначала длину L1(M) последовательности, для которой X1= 1,X2=M. Для этой последовательности получаем X3=M- 1,X4= 1,X5=M- 2, а значит,L1(M) =L1(M- 2) + 3 при M$\ge$3,L1(1) = 2,L1(2) = 4. Таким образом,
| L1(M) = $M=1$ |
Найдём теперь длину последовательности, для которой X1=M- 1,X2=M. Для этой последовательности X3= 1,X4=M- 1, то есть эта длина равна L1(M- 1) + 2 =L(M) при M> 1.
Таким образом, мы построили последовательность, длина которой равна L(M). Докажем теперь, что более длинной последовательности не существует, индукцией по M. Базу индукции M= 1, 2, 3 мы оставляем читателю в качестве упражнения. Пусть теперь M$\ge$4. Заметим сначала, что если X1<Mи X2<M, то все члены последовательности не превосходят M- 1, а значит, её длина не превосходит L(M- 1) <L(M). Если X1=M=X2, то длина последовательности равна двум, а значит, не больше L(M). Если X1=M,X2<M, то X3<M, а значит, длина последовательности не превосходит L(M- 1) + 1$\le$L(M). Таким образом, остался случай X1<M,X2=M. При X1= 1 и X1=M- 1 длина последовательности уже вычислена ранее и не превосходит L(M). Если же 1 <X1<M- 1, то X3<M- 1 и X4<M- 1, а значит, длина последовательности не превосходит 2 +L(M- 2) <L(M).
Итак, максимальная длина такой последовательности равна L(M).
Ответ
L(M) =$M=1$
Чтобы оставлять комментарии, войдите или зарегистрируйтесь