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

Существует ли последовательность $\{a_n\}$ натуральных чисел, удовлетворяющая следующим условиям:
а) в этой последовательности встречается каждое натуральное число и ровно один раз;
б) $a_1+a_2+\dots+a_n$ делится на $n^n$ для каждого $n=1, 2, 3, \dots $?

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

Построим $\{a_n\}$ индуктивно. Пусть $S_k$ - сумма первых $k$ чисел и $U$ -- множество еще не использованных чисел (изначально $U = \mathbb{N}$). Обозначим $m = \min U$.

$n^n \mid S_{n-1} + m$, тогда берем $a_n = m$ и $U = U \setminus \{m\}$.

Пусть $n^n \nmid S_{n-1} + m$. Рассмотрим систему:

\begin{align*}

x &\equiv -S_{n-1} \pmod{n^n} \\

x &\equiv -m - S_{n-1} \pmod{(n+1)^{n+1}}

\end{align*}

Т.к. $(n^n, (n+1)^{n+1}) = 1$, то по КТО система имеет бесконечно много решений, значит в $U$ найдется нужный $x$ ($x \neq m$, поскольку он не удовлетворяет первому сравнению). Тогда выберем $a_n = x$, $a_{n+1} = m$. $\blacksquare$

Построим $\{a_n\}$ индуктивно. Пусть $S_k$ - сумма первых $k$ чисел и $U$ - множество еще не использованных чисел (изначально $U = \mathbb{N}$). Обозначим $m = \min U$.

1) $n^n \mid S_{n-1} + m$, тогда берем $a_n = m$ и $U = U \setminus \{m\}$.

2) Пусть $n^n \nmid S_{n-1} + m$. Рассмотрим систему:

x ≡ S_(n-1) (mod n^n)

x ≡ -m - S_(n-1) (mod (n+1)^(n+1))

Т.к. $(n^n, (n+1)^{n+1}) = 1$, то по КТО система имеет бесконечно много решений, значит в $U$ найдется нужный $x$ ($x \neq m$, поскольку он не удовлетворяет первому сравнению). Тогда выберем $a_n = x$, $a_{n+1} = m$. $\blacksquare$