Делимость суммы на количество.

[Imperator]

maxal писал(а):

Вот решение из "Кванта" (задача M45):
http://kvant.mccme.ru/1971/07/p30.htm
http://kvant.mccme.ru/1971/08/p43.htm
http://kvant.mccme.ru/1971/08/p44.htm

Спасибо! Теперь точно все стало понятно.

[ddn]

Imperator писал(а):

Спасибо всем, кто ответили!
Для простого $n$ доказательство понятно. Осталось разобраться с доказательством ddn.

Мое доказательство с индукцией по делителям $n$ довольно простое, но слишком много формализма - моя вредная привычка. В кванте все изложено гораздо проще. Я подредактировал свой текст, исправил много синтаксических ошибок, описок, улучшил изложение - пусть останется.

Я здесь утверждал, что нашел тривиальное доказательство без индукции по $n$. Но при более внимательном рассмотрении это оказалось иллюзией. Извиняюсь.

Если рассмотреть аналогичное утверждение (для $n\geqslant 2$), но ограничится только наборами из чисел, все числа которых имеют остатки не больше $k$ (при $1\leqslant k\leqslant n-1$), то минимальный размер набора, у которого всегда есть поднабор из $n$ чисел с суммой кратной $n$ по прежнему останется равным $2\cdot n-1$, ибо набор из $n-1$ нулей и $n-1$ единиц (всего $2\cdot n-2$ чисел) таким свойством еще не обладает. Обозначим это утверждение как $P(n,k)$. То есть $P(n,k)\leftrightarrow f(n,k)=2\cdot n-1$. Я наивно полагал, что здесь можно использовать индукцию по $k$.

Действительно, начало индукции - для $k=1$ проходит удачно. В любом наборе, состоящем из $2\cdot n-1$ чисел только с остатками по $n$ равными 0 или 1, имеется либо по крайней мере $n$ чисел с остатками равными 0 по $n$, либо по крайней мере $n$ чисел с остатками равными 1 по $n$ - они и образуют поднабор с суммой чисел кратной $n$.
Я думал, что этот прием можно использовать и для любого $k\geqslant 2$ в шаге индукции.
В любом наборе, состоящем из $2\cdot n-1$ чисел с остатками по $n$ не большими $k$, имеется
1) либо, по крайней мере, $n$ чисел с остатками равными $k$ по $n$ - они образуют поднабор с суммой чисел кратной $n$,
2) либо, по крайней мере, $n$ чисел с остатками меньшими $k$ по $n$ - этот набор вроде можно рассматривать как результат применения посылки индукции $P(n,k-1)$, но... $P(n,k-1)$ не утверждает, что любой поднабор из $n$ чисел с остатками меньше $k$ будет иметь сумму кратную $n$, а утверждает лишь, что такой набор существует. В этом и была моя ошибка.
И пока что, доказательство в кванте - самое простое.
В кванте, для простых $n$ индукция используется только во вспомогательной лемме.

[maxal]

Двумерный вариант этой задачи предложен тут:
http://math.luga.ru/forum/viewtopic.php?t=2290