任给$n$个正整数，其中总存在$30$个之和是$30$的倍数

abababa

任给$n$个正整数，其中总存在$30$个之和是$30$的倍数，求$n$的最小值

realnumber

任给n个正整数，其中总存在2个之和是2的倍数，求n的最小值.
容易得到是3.比如0,1不行.(mod2)
任给n个正整数，其中总存在3个之和是3的倍数，求n的最小值.
是5.
比如0,0,1,1不行.(mod3)
任给n个正整数，其中总存在4个之和是4的倍数，求n的最小值.
是7.
比如0,0,0,1,1,1不可以.(mod4)
任给n个正整数，其中总存在5个之和是5的倍数，求n的最小值.
9
以上都可以证明.
1楼猜测是59.
58个的时候不行，比如29个0，29个1（mod30）.
59为什么成立。不会证明。前面3，4，5的时候是分类证明的，不好推广到30.

abababa

回复 2# realnumber
发一位网友maven昨天给我讲的，我看懂了
只考虑30的情况还算简单,但是推广到一般情况就变得复杂了,我先证明30的情况
当n=59时设这59个数为a1到 a59
由你证明的任意9数中必有5数之和能被5整除,先取出a1到9,从中取出5数之和是5的倍数,设此和为b1
除了这5数还有54数,再任取9数也必有5数和能被5整除,设此和为b2,重复操作得b1到b11,都能被5整除
由你证明的b1到b11有3数之和能被3整除,设这3数和为c1,重复操作得c1,c2,c3,都能被3整除
由你证明的3数中存在2数之和为偶数,不妨设c1+c2为偶数
于是c1,c2对应原59数中的30个,其和能被2*3*5 = 30整除

---

一般情况就是堆垒数论中著名的 EGZ 定理，下面的证明属于高维东，单墫也给过解析的证明。
解答．当 $n=p, p$ 为素数时，任取 $p$ 个数 $x_1 \rightarrow x_p$ 作和，共 $k=C_{2 p-1}^p$ 个和，分别记作 $S_1, S_2, \cdots S_k$若任意 $S_i$ 都不能被 $p$ 整除，则对每个 $i$ 有 $\operatorname{gcd}\left(S_i, p\right)=1$ ，由 Fermat 小定理知 $S_i^{p-1} \equiv 1(\bmod p)$ $k$ 式相加得 $\sum_{i=1}^k S_i^{p-1} \equiv k(\bmod p)$
左边展开得不同的同类项为 $x_1^{\alpha_1} x_2^{\alpha_2} x_3^{\alpha_3} \cdots x_p^{\alpha_p}$ ，合并同类项，每种同类项共 $C_{2 p-1-1}^{p-1}$ 个由于 $p \mid C_{2 p-1-1}^{p-1}$ ，即每种同类项系数都被 $p$ 整除，于是 $\sum_{i=1}^k S_i^{p-1} \equiv 0(\bmod p)$
但 $k=C_{2 p-1}^p=\frac{(2 p-1)(2 p-2) \cdots(p+1)}{1 \cdot 2 \cdots(p-1)}$ 不被 $p$ 整除，矛盾
于是存在一个 $S_i$ 能被 $p$ 整除，即 $n=p$ 时命题成立
假设 $n=p, q$ 时命题成立，则对于 $n=p q$ ，即给定 $n=2 p q-1$ 个整数时
每次取出 $2 p-1$ 个，由归纳假设知其中必有 $p$ 数之和被 $p$ 整除，记为数列 $a_1, a_2, \cdots, a_p$ ，剩下的 $p-1$ 个数放回如此操作，共能取 $\left[\frac{(2 p q-1)-(p-1)}{p}\right]=2 q-1$ 次，记第 $i$ 次取出的数列为 $a_{(p, i)}$ ，则
\[
\left\{\begin{array}{l}
a_{(1,1)}+a_{(2,1)}+\cdots+a_{(p, 1)}=p \cdot b_1 \\
a_{(1,2)}+a_{(2,2)}+\cdots+a_{(p, 2)}=p \cdot b_2 \\
\cdots \\
a_{(1,(2 q-1))}+a_{(2,(2 q-1))}+\cdots+a_{(p,(2 q-1))}=p \cdot b_{2 q-1}
\end{array}\right.
\]
其中 $\left\{b_i\right\}$ 是整数数列，由归纳假设知 $b_1, b_2, \cdots, b_{2 q-1}$ 中必有 $q$ 数之和能被 $q$ 整除，不妨设 $b_1+b_2+\cdots+b_q=q c$于是 $\sum_{j=1}^p \sum_{i=1}^q a_{(j, i)}=p q c$ ，即这 $p q$ 个数之和能被 $p q$ 整除
$n=1$ 时显然成立，从乘法归纳法知对任意正整数 $n$ 都成立