Республиканская олимпиада по математике, 2021 год, 9 класс

Дано натуральное число $n$. Последовательность $(x_1,x_2, \ldots, x_n)$ действительных чисел называется хорошей, если $x_1^3+x_2^3+\ldots +x_i^3=(x_1+x_2+ \ldots+ x_i)^2$ для каждого $i=1,2, \ldots,n$. Докажите, что количество различных хороших последовательностей не больше чем ${3^{n-1}+2^{n-1}}$. (Последовательности $(x_1,x_2, \ldots, x_n)$ и $(y_1,y_2, \ldots, y_n)$ считаются различными, если $x_i\ne y_i$ хотя бы для одного $i=1,2, \ldots, n$.) ( Н. Седракян )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Решение. Обозначим через $g(n)$ количество хороших последовательностей длины $n$. Индукцией по $i$ докажем, что все $x_i$ — целые числа и $$x_1 + x_2 + \ldots + x_i = \dfrac{j(j+1)}{2}$$ для некоторого $j \in \{ 0,1,\ldots ,i \}$.
    База. $i = 1$. Из условия получаем, что $x_1\in \{0,1 \$.
    Предположение. Пусть утверждение верно для $i$.
    Переход. Докажем для $i + 1$. По условию $${x_1}^3 + \ldots + {x_{i+1}}^3 = {(x_1 + \ldots + x_{i + 1})}^2 = {(x_1 + \ldots + x_i)}^2 + x_{i + 1} (x_{i + 1} + 2(x_1 + \ldots + x_i)) \Longrightarrow$$ $$\Longrightarrow {x_{i+1}}^3 = x_{i+1} (x_{i+1} + 2(x_1 + \ldots + x_i)) = x_{i+1}(x_{i+1} + j(j+1)). \quad (1)$$ Если $x_{i+1} = 0$, то переход доказан. Пусть теперь $x_{i+1} \ne 0$. Тогда из (1) получим, что ${x_{i+1}}^2 - x_{i+1} - j(j+1) = 0$, откуда $x_{i+1} = j+1$ или $x_{i+1} = -j$. Значит $x_{i+1}$ — целое, и $x_1 + \ldots + x_{i+1}$ равен одному из чисел $\dfrac{(j-1)j}{2},$ $\dfrac{j(j+1)}{2},$ $\dfrac{(j+1)(j+2)}{2}$ и $\dfrac{(j - 1)j}{2} = \dfrac{j(j + 1)}{2}$ при $j = 0$. Переход доказан.
    Пусть $f(i,j)$ — количество хороших последовательностей длины $i$ такие, что $x_1 + \ldots + x_i = \dfrac{j(j+1)}{2}$, где $0\le j \le i$. Тогда $$g(n) = f(n,0) + f(n,1) + \ldots + f(n,n).$$ Понятно, что $f(1,0) = f(1,1) = 1$. Рассмотрим состояние $f(i,j)$. По доказанному выше $x_{i+1}$ равен одному из чисел 0, $j+1$ или $-j$.
    Если $x_{i+1} = 0$, то мы получим состояние $f(i + 1,j)$.
    Если $x_{i+1} = j + 1$, то мы получим состояние $f(i + 1,j + 1)$.
    Пусть теперь $x_{i+1} = -j$ ($j > 0$, так как мы рассмотрели случаи $x_{i+1} = 0$). Тогда мы получим состояние $f(i + 1,j - 1)$. В итоге мы получим следующие рекуррентные соотношение: $$f(i + 1,0) = f(i,0) + f(i,1), \ f(i + 1,j) = f(i,j - 1) + f(i,j) + f(i,j + 1)$$ для всех $1\le j < i$, $$f(i + 1,i) = f(i,i - 1) + f(i,i), \ f(i + 1,i + 1) = f(i,i).$$ Индукцией по $k$ докажем, что $f(k,0) \ge 2^{k-1}$ и $g(k)\le 2^{k-1} + 3^{k-1}$.
    База: $k = 1$. $f(0,0) = 1, g(1) = 2$ все верно.
    Предположим, что утверждение верно для $k$. Докажем для $k+1$. Заметим, что $$f(1,0) = f(1,1) \text{ и } f(i + 1,1) = f(i + 1,0) + f(i,2) \ge f(i + 1,0).$$ Значит $f(k,1) \ge f(k,0) \ge 2^{k-1}$, следовательно, $f(k + 1,0) = f(k,0) + f(k,1) \ge 2^k$. Также $$g(k + 1) = f(k + 1,0) + \ldots + f(k + 1,k + 1) = 3(f(k,0) + \ldots + f(k,k)) - f(k,0) =$$ $$=3g(k) - f(k,0) \le 3(2^{k-1} + 3^{k-1}) - 2^{k-1} = 2^k + 3^k,$$ что и требовалось доказать.

Для $n=2$ получаем бесконечно много решений вида $x_1=-x_2$, аналогично для $n=2k$. По-моему, в задаче есть какая-то недосказанность

Вообще-то условие выполняется для каждого $i = 1, 2, ..., n$. В Вашем примере $x_1^3 = x_1^2$ и таких последовательностей конечно.

Решение тут:

http://respa2021.daryn.kz/protocols_result.php