Математикадан республикалық олимпиада, 2003-2004 оқу жылы, 11 сынып

Теменгі шарттарды қанағаттандыратын натурал сандардын $\left\{ {{a}_{n}} \right\}$ тізбегі табылады ма:
а) әрбір нагурал сан осы тізбекке кіреді және дәл бір рет қана кіреді;
б) әрбір $n=1,2,3,\ldots $ үшін ${{a}_{1}}+{{a}_{2}}+\ldots +{{a}_{n}}$ саны ${{n}^{n}}$ санына бөлінеді.

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

Построим $\{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$