Лемма. Если утверждение задачи верно для $n=a$ и для $n=b$, то оно верно и для $n=ab$.
Заметим, что свойство «сумма $n$ целых чисел $x_1$, $\ldots$, $x_n$ делится на $n$» можно формулировать и так: «среднее арифметическое $\dfrac{x_1+\ldots+x_n}{n}$ — целое число».
Итак, пусть даны произвольные $2ab-1$ целых чисел. Поскольку утверждение верно при $n=b$ и $2ab-1\gt2b-1$, из данных $2ab-1$ чисел можно выбрать $b$, сумма которых делится на $b$. Затем из оставшихся (если их не меньше $2b-1$) выберем ещё $b$ чисел, обладающих этим свойством, и т. д.
Поскольку
$$
2ab-1=(2a-1)b+(b-1),
$$
то эту операцию можно повторить $2a-1$ раз и получить $2a-1$ наборов по $b$ чисел, в каждом из которых среднее арифметическое $b$ чисел — целое. Поскольку утверждение верно для $n=a$, из этих $2a-1$ средних арифметических можно выбрать $a$, сумма которых делится на $a$. Ясно, что тогда $ab$ чисел, составляющих соответствующие $a$ наборов по $b$ чисел, обладают нужным свойством: их сумма делится на $ab$. Лемма доказана (эту лемму, так же как и задачу, придумал Ю. И. Ионин).
Итак, для того чтобы доказать утверждение задачи для произведения $n=a_1a_2\ldots a_k$, достаточно доказать его для отдельных сомножителей $n=a_1$, $n=a_2$, $\ldots$, $n=a_k$ (и несколько раз применить лемму). Поэтому достаточно научиться доказывать это утверждение для простых сомножителей числа $n$. Например, чтобы решить задачу для $n=100$, достаточно доказать два утверждения: «из любых 3 целых чисел можно выбрать 2, сумма которых делится на 2» и «из любых 9 целых чисел можно выбратьо 5 сумма которых делится на 5». Первое очевидно, а второе можно доказать не очень длинным перебором. Предоставляем читателю возможность убедиться в этом, а также попробовать придумать доказательство, которое годилось бы сразу для любого простого $n$. Одно такое доказательство мы изложим в следующем номере журнала.
(Продолжение. Начало решения см. в «Кванте» №7, стр. 30.)
Нам осталось доказать такой факт.
Теорема. Из $2p-1$ любых целых чисел можно выбрать $p$, сумма которых делится на $p$ ($p$ — произвольное простое число).
Приведём здесь доказательство, предложенное С. Ворониным (Москва).
Ясно, что в доказательстве мы можем рассматривать все числа «по модулю $p$», т. е. интересоваться только тем, какой из остатков 0, 1, 2, $\ldots$, $p-1$ даёт то или иное число при делении на $p$. Удобно представлять себе (особенно когда речь идёт о «сложении по модулю $p$»), что эти $p$ остатков расположены по кругу (рис. 8).
Рис. 8. Чтобы найти сумму $a+b$ по модулю $p$, нужно отсчитать от $a$ против часовой стрелки $b$ единиц (на этом рисунке, соответствующем $p=11$, изображена сумма $8+8$, которая по модулю 11 равна 5).
Лемма. Пусть даны $r$ целых чисел $b_1$, $b_2$, $\ldots$, $b_r$; $0\lt b_i\lt p$ для всех $i=1$, 2, $\ldots$, $r$ и $0\lt r\lt p$ ($p$ — простое). Тогда из этих чисел можно составить по крайней мере $r+1$ сумм, дающих различные остатки при делении на $p$ (при этом разрешается брать сумму «пустого множества слагаемых», которая считается равной нулю, суммы из одного слагаемого, из двух, $\ldots$, из всех $r$ слагаемых).
Доказательство. При $r=1$ это очевидно: суммы дают остатки 0 и $b_1$. Предположим, что это верно для $r=k\lt p-1$ и неверно для $r=k+1$, и придём к противоречию. Пусть суммы из $k$ слагаемых $b_1$, $b_2$, $\ldots$, $b_k$ дают $k+1$ различных остатков 0, $s_1$, $\ldots$, $s_k$. Тогда, поскольку после присоединения $b=b_{k+1}$, количество различных сумм не должно увеличиться, все суммы
$$
0+b,~s_1+b,~\ldots,~s_k+b
$$
(по модулю $p$) содержатся во множестве
$$
\{0,s_1,\ldots,s_k\}.
$$
Другими словами, если к любому элементу этого множества прибавить $b$, то снова получится элемент того же множества (попробуйте представить себе такое множество на рисунке 8). Таким образом, это множество заведомо содержит элементы 0, $b$, $2b$, $3b$, $\ldots$, $(p-1)b$. Но ясно, что все эти элементы различны (по модулю): разность
$$
ib-jb=(i-j)b,
$$
где $0\lt i-j\lt p$ и $0\lt b\lt p$, не может делиться на $p$, поскольку $p$ простое. Таким образом, мы доказали, что множество $\{0,s_1,\ldots,s_k\}$ содержит все $p$ различных элементов, хотя предполагали, что $$
k+1\lt p.
$$
Лемма доказана.
Доказательство теоремы. Пусть
$$
a_1\le a_2\le\ldots\le a_p\le a_{p+1}\le \ldots\le a_{2p-1}
$$
— остатки от деления данных $2p-1$ чисел на $p$. Рассмотрим ещё $p$ таких чисел:
$$
a_{p+1}-a_2,~a_{p+2}-a_3,~\ldots,~a_{2p-1}-a_p.\tag{*}
$$
Если какое-нибудь одно из них равно нулю, например
$$
a_{p+l}-a_{l+1}=0,
$$
то $$
a_{l+1}=a_{l+2}=a_{l+3}=\ldots=a_{l+p},
$$
и сумма соответствующих $p$ чисел делится на $p$. Осталось рассмотреть случай, когда все числа (*) отличны от нуля.
Найдём остаток $x$ от деления суммы $a_1+a_2+\ldots+a_p$ на $p$. Если $x=0$, то всё ясно. Если $x\ne0$, то, пользуясь леммой, мы можем составить из разностей (*) сумму, дающую остаток $p-x$ при делении на $p$. Добавив соответствующие разности к $a_1+a_2+\ldots+a_p$ и проведя очевидные сокращения, мы получим сумму $p$ слагаемых, делящуюся на $p$.
Пользуясь результатом задачи М45, нетрудно установить, что утверждение «Из любых $a$ целых чисел можно выбрать $b$ чисел, сумма которых делится на $c$» (где $a$, $b$, $c$ — конкретные натуральные числа) верно тогда и только тогда, когда $b$ делится на $c$ и $a\ge b+c-1$.
