Последовательность целых частей корней из суммы предыдущих

[worm2]

Дано: $a_1 = 1$, $a_k=\lfloor\sqrt{a_1+a_2+\ldots+a_{k-1}}\rfloor$ при k > 1. Найти $a_{1000}$.

Задача XXIX-й Московской математической олимпиады (1966 г.). Предлагалась учащимся 8 класса.

[Руст]

Это очень простая задача. Поэтому не удивительно, что предлагалась для восьмого класса.

[worm2]

Руст писал(а):

Это очень простая задача. Поэтому не удивительно, что предлагалась для восьмого класса.

Ну не знаю. Конечно, раз предполагается, что задача может быть решена восьмиклассником за ограниченное время, то это не уровень, скажем, проблем Гильберта.

Но там есть нюанс, как говорил Чапаев. Задача снабжена звёздочкой. А несколько видоизменённый вариант предлагался IX-XI классам (правда, уже без звёздочки).

В общем, я надеюсь, что найдутся люди, которых эта задача заинтересует.

[Руст]

На счёт очень простая погрячился. Ответ такой: $a_m=2^{k-1}+[\frac{m-2^k-k}{2}], \ 2^k+k\le m\le 2^{k+1}+k, \ k>0 .$

[RIP]

Но и сложной я бы задачу не назвал. Но задача, конечно, очень красивая.
Решение может быть, например, таким.
1) Посл-ть $a_n$ неубывает.
2) При $n\geqslant2$

$$a_1+\ldots+a_{n-1}<(a_n+1)^2\quad\Longrightarrow\quad a_1+\ldots+a_n<(a_n+2)^2\quad\Longrightarrow\quad a_{n+1}\leqslant a_n+1$$

3) Пусть число $s\in\mathbb{N}$ встречается в посл-ти $k_s\in\mathbb{N}$ раз.
Если обозначить $A_s=1\cdot k_1+2\cdot k_2+\ldots+s\cdot k_s$, то $k_s$-наименьшее целое такое, что $A_s=A_{s-1}+sk_s\geqslant(s+1)^2$.
Сделаем замену $k_s=2+l_s,\ B_s=1\cdot l_1+2\cdot l_2+\ldots+s\cdot l_s$. Тогда условие перепишется в виде $B_s=B_{s-1}+sl_s\geqslant s+1$.
Тогда $l_1=B_1=2$ и по индукции легко доказывается
Утв. При $\forall s\in\mathbb{N}$: (1) $l_{2^s}=1$; (2) $l_{j}=0,\ 2^s<j<2^{s+1}$; (3) $B_j=2^{s+1}$, $2^s\leqslant j<2^{s+1}$.$\qed$

Поэтому $k_1+k_2+\ldots+k_N=2N+2+\lfloor\log_2N\rfloor$.
4) $a_n=N$ равносильно $k_1+k_2+\ldots+k_{N-1}<n\leqslant k_1+k_2+\ldots+k_N$, откуда и получаем ответ.
Только его можно упростить $a_m=\lfloor\frac{m-k}2\rfloor$ (в обозначениях Руста)

[Whitaker]

RIP в сообщении #50728 писал(а):

2) При $n\geqslant2$

$$a_1+\ldots+a_{n-1}<(a_n+1)^2\quad\Longrightarrow\quad a_1+\ldots+a_n<(a_n+2)^2\quad\Longrightarrow\quad a_{n+1}\leqslant a_n+1$$

Уважаемый RIP!
Первые два неравенства я понял.
А откуда Вы получили последнее неравенство?
Ведь из второго выводится то, что $a_{n+1}\leq a_n+2$!
Я не могу понять, как Вы получили последнее неравенство.

[RIP]

Whitaker в сообщении #539013 писал(а):

Ведь из второго выводится то, что $a_{n+1}\leq a_n+2$!

Там нер-во строгое. А числа у нас целые.

[Whitaker]

Почему строгое?
Мы извлекаем корень, а затем берем целую часть числа.
А ведь целая часть числа - функция неубывающая.

[RIP]

$a_{n+1}\le\sqrt{a_1+\ldots+a_n}<a_n+2$.

[Whitaker]

RIP большое Вам спасибо!
Теперь мне понятно!