Задача 78594

Темы:    [ Рекуррентные соотношения (прочее) ] [ Индукция (прочее) ] [ Иррациональные неравенства ]

Сложность: 5- Классы: 8,9,10

Условие

Дано: $$ a_1=1,a_k=\left[\sqrt{a_1+a_2+\dots +a_{k-1}}\right].$$

Найти $a_{1000}$.

Примечание. $\left[A\right]$ — целая часть $A$.

Решение

Ответ: 495. Докажем по индукции, что начальный отрезок нашей последовательности имеет вид $1$, $1$, $1$, $1$, $2$, $2$, $2$, $3$, $3$, $4$, $4$, $4$, $5$, $5$, $6$, $6$, $7$, $7$,... , где единица встречается 4 раза, числа вида $2^k$ – три раза, а остальные натуральные числа – по два раза. Пусть мы уже доказали, что начальный отрезок нашей последовательности имеет вид $1$, $1$, $1$, $1$, $2$, $2$, $2$, $3$, $3$,...,$n--1$, $n$, $n$. Найдем ее следующий член. Возьмем наибольшее $k$ для которого $2^k < n$. Сумма выписанных чисел равна $$s= 2(1 + 2 +...+n) + 1 + 2 +...+ 2^{k + 1}=n \cdot (n+1)+2^{k+1}.$$ Если $n=2^{k+1}$, то $n^2 < s < (n+1)^2$, то есть следующий член последовательности равен $n$. Иначе $n+1 \leq 2^{k+1} < 2 n$, и $(n+1)^2 \leq s < (n+2)^2$, то есть следующий член последовательности равен $n+1$. Аналогично находятся следующие члены последовательностей $1$, $1$, $1$, $1$, $2$, $2$, $2$,... $n-1$, $n$ и $1$, $1$, $1$, $1$, $2$, $2$, $2$,... $n-1$, $n$, $n$, $n$. Из явного вида последовательности число $a_{1000}$ находится простым подсчетом.

Ответ

Ответ: 495.

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

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