Областная олимпиада по математике, 2017 год, 11 класс

Дана последовательность ${{x}_{n}}~\left( n=1,2,\ldots \right)$, в которой ${{x}_{1}}=0.$ Известно, что для всех целых $n > 1$ ${{x}_{n}}={{x}_{n-1}}+\left[ \dfrac{{{n}^{2}}}{4} \right].$ (Здесь $\left[ a \right]$ означает наибольшее целое число, не превосходящее $a$). Определите все значения $n$, при которых ${{x}_{n}}$ делится на $n$.

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

$Ответ:n=1;3;8m+6,$ где $m$ не делится на $3$.

Заметим такие факты:

$x_{2k}=x_{2k-1}+[\dfrac{4k^2}{4}]=x_{2k-1}+k^2$

$x_{2k+1}=x_{2k}+[\dfrac{4k^2+4k+1}{4}]=x_{2k}+k^2+k$. Используя это:

$x_{2k+1}= x_{2k-1}+2k^2+k= ...=(2k^2+k)+(2(k-1)^2+k-1)+...+(2*1^2+1)+x_{1}= 2(k^2+...+1^2)+(k+...+1)= \dfrac{k(2k+1)(k+1)}{3}+\dfrac{k(k+1)}{2} =\dfrac{k(k+1)(4k+5)}{6}$

Понятно что: $x_{2k}=k^2+\dfrac{(k-1)k(4k+1)}{6}$. Рассмотрим 2 случая:

$I)n=2k+1$. Тогда если $x_{n}$ делится на $n$, то $k(k+1)(4k+5)$ делится на $2k+1$. Из чего выходит что $2k(2k+2)(4k+5)$ делится на $2k+1$ что эквивалентно $3$ делится на $2k+1$. Далее перебором находим ответы.

$II)n=2k$. Если $k=2^xy$, где $x$ натуральное $y$ нечётное, То $k^2$ делится на $2^{x+1}$. Из чего выходит что $\dfrac{(k-1)k(4k+1)}{6}$ делится на $2^{x+1}$. Но так как $(k-1,2)=(4k+1,2)=1$, то $\dfrac{k}{6}$ должно делится на $2^{x+1}$, что невозможно.

Теперь можно считать $k=2l+1$, $x_{4l+2}=4l^2+4l+1+\dfrac{(2l+1)l(8l+5)}{3} \equiv 2l+1+\dfrac{(2l+1)l(8l+5)}{3}=S \pmod4l+2$ $(1)$ . Пусть $2l+1=3^pq$, где $p$ натуральное число, п $q$ Натуральное число которое не делится на 3. Очевидно что $\dfrac{(2l+1)l(8l+5)}{3}$ должно делится на $3^p$. Но это эквивалентна $\dfrac{l}{3}$ делится на $3^p$, (так как $(3,l)=(3,8l+5)=1$), что невозможно.

Значит можно считать что $2l+1$ Не делится на $3$. Очевидно что $S$ Делится на $2l+1$. Теперь при рассмотрении $mod2$ можно легко найти что $l$ нечётно. Из этих фактов вытекает что $4l+2=8m+6$, где $m$ не делится на $3$.

В 3-й строке снизу должно быть так: $x_{4l+2}=4l^2+4l+1+S\equiv -2l-1+S\pmod{4l+2}.$

На самом деле во втором случае ответов бесконечно много. Для этого надо рассмотреть делимость $x_{4l+2}$ на $2,$ и на $2l+1$ отдельно.

Спасибо что указали ошибку. Исправил.