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

[Imperator]

Доказать, что среди $2n-1$ различных целых чисел можно выбрать $n$ таких, что их сумма будет делиться на $n$.

[TOTAL]

Imperator писал(а):

Доказать, что среди $2n-1$ различных целых чисел можно выбрать $n$ таких, что их сумма будет делиться на $n$.

Я могу доказать только для простого $n$

[bot]

Индукция. Без ограничения общности можно считать, что чётных больше, чем нечётных, иначе отнимем от всех по единице. Выбираем теперь n чётных и все делим пополам.

P.S. Условие различности излишне.

[RIP]

http://dxdy.ru/viewtopic.php?t=7670&hig ... 0%ED%F2%2A

[bot]

О-о-п-с, ерунду написал.

[TOTAL]

bot писал(а):

Индукция. Без ограничения общности можно считать, что чётных больше, чем нечётных, иначе отнимем от всех по единице. Выбираем теперь n чётных и все делим пополам.

$n=4$ числа: $1, 1, 1, 2, 2, 2, 0$.
Что тут выбирать и делить пополам?

[Батороев]

Исходное утверждение порождает другое, а именно:

Среди $ 2n_1 + 1$ различных чисел можно выбрать $ n_1 $ таких, что их сумма $ C_1 $ будет удовлетворять условию сравнения $ C_1\equiv i (mod (n_1+1)) $, где $ i = 1, 2, 3, ... (n_1+1) $ (1)

Т. е. допустим, что сумма $ 2n - 1 $ чисел имеет остаток $ C_0\equiv i (mod n) $.
Если справедливо утверждение (1) и $ n_1 = n -1$, то из $ 2n -1 $ ($ 2n_1 +1 $) чисел можно выбрать $ n - 1 $ таких чисел, что их сумма будет $ C_1\equiv i (mod n) $,
а следовательно, оставшиеся $ n $ чисел будут иметь сумму $ C_n\equiv 0 (mod n) $.

[TOTAL]

Батороев писал(а):

Исходное утверждение порождает другое, а именно:

Среди $ 2n_1 + 1$ различных чисел можно выбрать $ n_1 $ таких, что их сумма $ C_1 $ будет удовлетворять условию сравнения $ C_1\equiv i (mod (n_1+1)) $, где $ i = 1, 2, 3, ... (n_1+1) $ (1)

Это неверное утверждение

[ddn]

bot писал(а):

Индукция. Без ограничения общности можно считать, что чётных больше, чем нечётных, иначе отнимем от всех по единице. Выбираем теперь n чётных и все делим пополам.

P.S. Условие различности излишне.

Да, возможно, что и есть доказательство по индукции, но только не по предыдущему числу, а по делителям числа n.

[Батороев]

TOTAL писал(а):

Батороев писал(а):

Исходное утверждение порождает другое, а именно:

Среди $ 2n_1 + 1$ различных чисел можно выбрать $ n_1 $ таких, что их сумма $ C_1 $ будет удовлетворять условию сравнения $ C_1\equiv i (mod (n_1+1)) $, где $ i = 1, 2, 3, ... (n_1+1) $ (1)

Это неверное утверждение

В чем, на Ваш взгляд, заключается неверность утверждения (1)?

[Brukvalub]

Да просто возьмите

\[n_1 = 2\]

и 5 разных чисел, делящихся на 3, и попробуйте реализовать ваше утв. для i=2.

[Батороев]

Brukvalub писал(а):

Да просто возьмите

\[n_1 = 2\]

и 5 разных чисел, делящихся на 3, и попробуйте реализовать ваше утв. для i=2.

Остается процитировать bot'a в отношении себя:

bot писал(а):

О-о-п-с, ерунду написал.

и подправить:
Среди $ 2n_1 +1 $ чисел, имеющих сумму $ C_0\equiv i (mod (n_1+1)) $, можно выбрать $ n_1 $ таких чисел, что их сумма $ C_1 $ будет удовлетворять условию сравнения $ C_1\equiv i (mod (n_1+1)) $.

[ddn]

Обозначим целочисленный интервал от $1$ до $n$ через $\overline{n}=\{i|_{i=1}^n\}$, множеством индексов $\mathbb{I}$ будем называть любое подмножество натуральных чисел $\mathbb{I}\subseteq\mathbb{N}$.
Набором (целых чисел) $A$ - отображение $A=\{(i,A(i))|_{i\in\mathbb{I}}\}$, принадлежащее $A\in (\mathbb{I}\to\mathbb{Z}) \equiv \mathbb{Z}^\mathbb{I}$, тогда $bas(A)=\mathbb{I}$ - база индексов набора $A$, $dim(A)=card(\mathbb{I})\geqslant 0$ - величина набора $A$, a $S(A)=\sum\limits_{i\in\mathbb{I}} A(i)$ - сумма набора $A$. Набор $A$ с базой вида $\overline{n}$ отождествим с обычным вектором $A=(A_i|_{i=1}^ n)$.
Поднабором $B$ некоторого набора $A$, называется набор, определенный на множестве индексов $\mathbb{I}'$ и являющийся сужением отображения $A$ на это множество индексов $\mathbb{I}'$, которое включено в базу индексов $bas(A)=\mathbb{I}$ набора $A$, то есть:
$bas(B)=\mathbb{I}' \subseteq bas(A)=\mathbb{I}$ и $B=A|_{\mathbb{I}'}$ (то есть $B(i)=A(i)$ при $i\in\mathbb{I}'$)

Пусть $n\in \mathbb{N}$, определим для каждого натурального $n$ функцию $f\in (\mathbb{N}\to \mathbb{N}_0)$ дающую минимальное из таких целых неотрицательных $m$ (если они существуют), что произвольный набор $A$ такой величины $m$ обладает поднабором величины $n$ с суммой его чисел кратной $n$:
$f(n)=min(m|m\in\mathbb{N}_0, \forall A\in \mathbb{Z}^{\overline{m}} \exists \mathbb{I}\subseteq \overline{m} (card(\mathbb{I})=n\wedge \sum\limits_{i\in\mathbb{I}} A_i \equiv 0\ mod\ n))$;
$f(n)$ определено, если найдется хоть одно такое $m$, а то, что оно найдется, сейчас докажем.

Очевидно $f(1)=0$ так как уже пустое множество $\emptyset$ дает нужную сумму: $(\sum\limits_{i\in \emptyset} i)=0 \equiv 0\ mod\ 1$. Также очевидно $n\leqslant f(n)$.
Для натуральных, имеющих ненулевые остатки, то есть для $n\geqslant 2$ имеем ограничение снизу: $2\cdot n-1\leqslant f(n)$ (заметим, что $2\cdot n-1>n$) так как для $m=2\cdot n-2$ есть контрпример - набор $A=(0|_{i=1}^{n-1},1|_{i=1}^{n-1})$, суммы всех поднаборов величины $n$ которого находятся в диапазоне от 1 до $n-1$;
и также имеем ограничение сверху $f(n)\leqslant n\cdot (n-1)+1$, так как в этом случае среди $n$ непересекающихся поднаборов чисел с одинаковыми остатками по $n$ всегда найдется поднабор величины не меньше $n$, а сумма любых его $n$ чисел очевидно кратна $n$, и продолжая выкладки получим:
$f(n)\leqslant (n-1)\cdot n+1=n^2-n+1=n^{\frac{ln(n^2-n+1)}{ln(n)}} \left{_{\geqslant n^{log_2(3)}}^{<n^2}$,
последние неравенства следуют из $\frac{ln(n^2-n+1)}{ln(n)}\left|_{n=2}= log_2(3)$ и $\frac{ln(n^2-n+1)}{ln(n)}\uparrow$ при $n\uparrow$ и $n>0$,
и также из $n^2-n+1<n^2$ при $n>1$. Оценка сверху, как видите, не самая лучшая.
Но из этих оценок можно уже найти $f(2)$:
$2\cdot 2-1\leqslant f(2)\leqslant 2^2-2+1$, $\Leftrightarrow 3\leqslant f(2)\leqslant 3$, $\Rightarrow f(2)=3$.

Определим для любых натурального $n\in \mathbb{N}$ и набора $A\subseteq\mathbb{Z}^{\mathbb{I}}$, c базой $\mathbb{I}$ и величиной $m\equiv dim(A)\geqslant f(n)$ оператор выбора $\mathfrak{F}(A,n)$, дающий такой поднабор $B$ набора $A$ величиной $n$ и с некоторой базой $\mathbb{I}'$, что сумма этого поднабора кратна $n$, то есть:
$\mathfrak{F}(A,n)\equiv B=A|_{\mathbb{I}'}$, $\dim(B)\equiv card(\mathbb{I}')=n$ и $S(B)=\sum\limits_{i\in\mathbb{I}'} A(i) \equiv 0\ mod\ n$.

Применим индукцию по делителям $n$ и посмотрим, что можно получить.
Пусть $n$ натуральное составное, то есть $n=a\cdot b$, где $a\geqslant 2 $ и $b\geqslant 2$, тогда очевидно что $n>a$ и $n>b$.
Пусть натуральное $m=f(a)\cdot b+f(b)-b$ и рассмотрим произвольный набор $A=(A_i|_{i=1}^m)$ - то есть, набор величины $m$ с базой $\overline{m}$. Докажем что $f(a\cdot b)\leqslant m$.
Выберем из набора $A$ последовательно, по индукции, непересекающиеся поднаборов $B_{\cdot}= B_i|_{i=1}^{f(a)}$ в количестве $f(a)$ с базами $\mathbb{I}_{\cdot}=\mathbb{I}_i|_{i=1}^{f(a)}$ величиной $b$ и суммой $b$ каждый, то есть:
$B_i=\mathfrak{F}(A|_{\mathbb{I}/\bigcup\limits_{j=1}^{i-1} \mathbb{I}_j},b)}$,
где $bas(B_i)=\mathbb{I}_i$, $\ dim(B_i)\equiv\mathbb{I}_i=b$, $\ S(B_i)\equiv 0\ mod\ n$, (где $i=1..f(a)$);
здесь по построению $\mathbb{I}_i\cap \mathbb{I}_{i'}=\emptyset$ (где $i, i'=1..f(a)$ и $i\not =i'$);
чтобы оператор $\mathfrak{F}$ был определен для каждого $i=1..f(a)$, то есть для каждого набора $A|_{\mathbb{I}/\bigcup\limits_{j=1}^{i-1} \mathbb{I}_j}$ величины $m-(i-1)\cdot b$ необходимо чтобы $min(m-(i-1)\cdot b|_{i=1}^{f(a)})\geqslant f(b)$, $\Leftrightarrow m-(f(a)-1)\cdot b\geqslant f(b)$, $\Leftrightarrow m\geqslant (f(a)-1)\cdot b+f(b)$ - это ограничение и было взято на размер набора $A$.

Сформируем набор $C$ с базой $\overline{f(a)}$ из сумм $S(B_i)$ и поднабор $K=C/b\ mod\ a$ (поэлементно) с той же базой, то есть:
$C=\{(i,S(B_i))|_{i=1}^{f(a)}\}$ и $K=\{(i,S(B_i)/b\ mod\ a)|_{i=1}^{f(a)}\}$,
отсюда же $C(i)/b\equiv S(B_i)/b=q\cdot a+K(i)$, $C(i)\equiv S(B_i)=q\cdot a\cdot b+K(i)\cdot b\equiv K(i)\cdot b\ mod\ n$ и значит $C\equiv K\cdot b\ mod\ n$.
Выделяем из набора $K$ величины $f(a)$ поднабор $K'=\mathfrak{F}(K,a)$ с некоторой базой $\mathbb{J}$ величиной $a$ с суммой $S(K')=a$, что для набора $C$ соответствует поднабору $C'=C|_{\mathbb{J}}$ с той же базой $\mathbb{J}$ и суммой $S(C')\equiv S(K')\cdot b\ mod\ n\equiv a\cdot b\ mod\ n\equiv 0\ mod\ n$.
Но та же сумма $S(C')$ совпадает с суммой поднабора $A'$ набора $A$ имеющего базу $\mathbb{I}'=\bigcup\limits_{i\in\mathbb{J}}\mathbb{I}_i$, действительно:
$S(C')=\sum\limits_{i\in\mathbb{J}} S(B_i)=\sum\limits_{i\in\mathbb{J}} \sum\limits_{j\in\mathbb{I}_i} A(j)=\sum\limits_{i\in\mathbb{I}'}A(i)=S(A')$.
Значит, сумма поднабора $S(A')\equiv 0\ mod\ n$, а величина поднабора $A'$ равна $dim(A')=card(\mathbb{I}')=card(\mathbb{J})\cdot card(\mathbb{I}_i)=a\cdot b=n$.
То есть мы доказали $f(a\cdot b)\leqslant f(a)\cdot b+f(b)-b$.

Если теперь предположить $f(a)=2\cdot a-1$ и $f(b)=2\cdot b-1$, то получим $f(a\cdot b)\leqslant (2\cdot a-1)\cdot b+2\cdot b-1-b=2\cdot a\cdot b-1$ и учитывая $2\cdot a\cdot b-1\leqslant f(a\cdot b)$ получим $f(a\cdot b)=2\cdot a\cdot b-1$ или же $f(n)=2\cdot n-1$.

Теперь можно провести индукцию.
Предикат индукции $P(n)\leftrightarrow f(n)=2\cdot n-1$.

Начало индуции: допустим, что $P(p)$ выполняется для всех простых $p$, то есть
$\forall n (\tau(n)=1\Rightarrow P(n))$; для $n=2$ уже доказано.

Шаг индукции сделаем, либо по числу простых множителей натурального числа:
$\forall n (\tau (n)=k-1\geqslant 1\Rightarrow P(n)) \Rightarrow \forall n (\tau(n)=k\Rightarrow P(n))$,
либо по его собственной величине:
$\forall k (2\leqslant k<n\Rightarrow P(k)) \Rightarrow P(n)$.

Тогда доказываем общее утверждение:
$\forall n (\tau(n)\geqslant 1\Rightarrow P(n))$, или
$\forall n (n\geqslant 2\Rightarrow P(n))$.

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

[Imperator]

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

[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