Информация о задаче

Задача 78624

Темы:	[	Примеры и контрпримеры. Конструкции	]
	[	Индукция (прочее)	]
	[	Целая и дробная части. Принцип Архимеда	]

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

Прислать комментарий

Условие

Дана последовательность целых положительных чисел X₁, X₂...X_n, все элементы которой не превосходят некоторого числа M. Известно, что при всех k > 2 X_k = | X_{k - 1} - X_{k - 2}|. Какой может быть максимальная длина этой последовательности?

Решение

Обозначим через $\lceil$ x $\rceil$ наименьшее целое число, не меньшее x, а через $\lfloor$ x $\rfloor$ — наибольшее целое число, не превосходящее x. Докажем, что наибольшая длина L(M) такой последовательности равна

L(M) = $\begin{displaymath}\begin{cases} 2,&{\rm если~$M=1$,}\\ \left\lceil\frac{3M}{2}\right\rceil+1,&{\rm если~$M>1$.} \end{cases}\end{displaymath}$

Найдём сначала длину L₁(M) последовательности, для которой X₁ = 1, X₂ = M. Для этой последовательности получаем X₃ = M - 1, X₄ = 1, X₅ = M - 2, а значит, L₁(M) = L₁(M - 2) + 3 при M $\ge$ 3, L₁(1) = 2, L₁(2) = 4. Таким образом,

L₁(M) = $\begin{displaymath}\begin{cases} 2,&{\rm если~$M=1$,}\\ \left\lfloor\frac{3M}{2}\right\rfloor+1,&{\rm если~$M>1$.} \end{cases}\end{displaymath}$

Найдём теперь длину последовательности, для которой X₁ = M - 1, X₂ = M. Для этой последовательности X₃ = 1, X₄ = M - 1, то есть эта длина равна L₁(M - 1) + 2 = L(M) при M > 1. Таким образом, мы построили последовательность, длина которой равна L(M). Докажем теперь, что более длинной последовательности не существует, индукцией по M. Базу индукции M = 1, 2, 3 мы оставляем читателю в качестве упражнения. Пусть теперь M $\ge$ 4. Заметим сначала, что если X₁ < M и X₂ < M, то все члены последовательности не превосходят M - 1, а значит, её длина не превосходит L(M - 1) < L(M). Если X₁ = M = X₂, то длина последовательности равна двум, а значит, не больше L(M). Если X₁ = M, X₂ < M, то X₃ < M, а значит, длина последовательности не превосходит L(M - 1) + 1 $\le$ L(M). Таким образом, остался случай X₁ < M, X₂ = M. При X₁ = 1 и X₁ = M - 1 длина последовательности уже вычислена ранее и не превосходит L(M). Если же 1 < X₁ < M - 1, то X₃ < M - 1 и X₄ < M - 1, а значит, длина последовательности не превосходит 2 + L(M - 2) < L(M). Итак, максимальная длина такой последовательности равна L(M).

Ответ

L(M) = $\begin{displaymath}\begin{cases} 2,&{\rm если~$M=1$,}\\ \left\lceil\frac{3M}{2}\right\rceil+1,&{\rm если~$M>1$.} \end{cases}\end{displaymath}$

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


олимпиада
Название	Московская математическая олимпиада
год
Номер	30
Год	1967
вариант
	1
Класс	9
Тур	2
задача
Номер	2