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

Дана последовательность ${{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$

Для решения нам понадобится следующий факт:

$$\left \lfloor \frac{n^2}{4} \right \rfloor = \left\{ \begin{gathered} \frac{n^2}{4}, 2 \mid n \\ \frac{n^2 - 1}{4}, 2\nmid n \end{gathered}\right.$$

Отсюда выходит явная формула для $x_{n}$,

$$x_{n} = \sum_{i = 1}^n \left \lfloor \frac{i^2}{4} \right \rfloor = \left\{ \begin{gathered} \frac{n^2}{4} + \frac{(n - 1)^2 - 1}{4} + \ldots + \frac{2^2}{4} + \frac{1^2 -1 }{4}, 2 \mid n \\ \frac{n^2 - 1}{4} + \frac{(n-1)^2}{4} + \ldots + \frac{1^2 - 1}{2}, 2\nmid n \end{gathered}\right. \iff \left\{ \begin{gathered} \frac{\sum_{i = 1}^n (i^2) - \frac{n}{2}}{4}, 2 \mid n \\ \frac{\sum_{i = 1}^n (i^2) - \frac{n+1}{2}}{4}, 2\nmid n \end{gathered}\right. \iff$$

$$\left\{ \begin{gathered} \frac{\frac{n(n+1)(2n + 1)}{6} - \frac{n}{2}}{4}, 2 \mid n \\ \frac{\frac{n(n+1)(2n + 1)}{6} - \frac{n + 1}{2}}{4}, 2\nmid n \end{gathered}\right. \iff \left\{ \begin{gathered} \frac{n(2n^2 + 3n - 2)}{24}, 2 \mid n \\ \frac{n(2n^2 + 3n - 2) - 3}{24}, 2\nmid n \end{gathered}\right.$$

Разберем отдельно $2 \nmid n$ и $2 \mid n$

$$1. 2 \nmid n$$

Тогда $n \mid \frac{n(2n^2 + 3n - 2) - 3}{24} \implies n \mid (n(2n^2 + 3n - 2) - 3) \implies n \mid 3 \implies n = 1, 3$

Если $n = 1: 1 \mid x_{1} = 0$ - подходит

Если $n = 3: 3\mid x_{3} = 3$ - подходит

$$2. 2 \mid n$$

$n \mid \frac{n(2n^2 + 3n - 2)}{24} \iff i) 3 \mid 2n^2 + 3n - 2$ $ ii) 8 \mid 2n^2 + 3n - 2$ - выполняются одновременно. Поймем по отдельности

$i)$

$n \equiv 0 (mod 3) \implies 2n^2 + 3n - 2 \equiv 1 \not\equiv 0 (mod 3)$

$n \equiv 1(mod 3) \implies 2n^2 + 3n - 2 \equiv 0 (mod 3)$ - подходит

$n \equiv 2 (mod 3) \implies 2n^2 + 3n - 2 \equiv 0 (mod 3)$ - подходит

$ii)$ Так как $2 \mid n$, то достаточно перебрать только четные остатки

$n \equiv 0 (mod 8) \implies 2n^2 + 3n - 2 \equiv 6 \not\equiv 0 (mod 8)$

$n \equiv 2 (mod 8) \implies 2n^2 + 3n - 2 \equiv 4 \not\equiv 0 (mod 8)$

$n \equiv 4 (mod 8) \implies 2n^2 + 3n - 2 \equiv 2 \not\equiv 0 (mod 8)$

$n \equiv 6 (mod 8) \implies 2n^2 + 3n - 2 \equiv 0 \implies n \equiv 6 (mod 8)$

Так как $i) n \equiv 1, 2 (mod 3)$ $ii) n \equiv 6 (mod 8) \implies \nexists n \in \mathbb{N} : n \mid x_{n}$

у тебя есть ошибка, посмотри моё решение этой задачи в 11-классе