證明：在任意 15個整數中，必有8個整數的和是8的倍數？

01-07

RT或者能否推廣到任意2n－1個整數中，必有n個整數的和是n的倍數
3 2 2
5 3 3

都比較好推出，9 5 5開始就混亂了。哎感覺沒有把握好抽屜原理的精髓orz

歸納法：我們證明對任意 $n=2^m$ ，在任意 $2n-1$ 個數中必有 $n$ 個數之和被 $n$ 整除。

證明：當m=0時trivial。我們現在從m推出m+1，顯然 $2*2^{m+1}-1>2*2^m-1$ 個數中有 $2^m$ 個數之和被 $2^m$ 整除，記為 $a_1$ 。

進一步 $2*2^{m+1}-2^m-1>2^m-1$ ，我們在剩下的數中找到 $2^m$ 個數使其和被 $2^m$ 整除，記為 $a_2$ 。

再進一步 $2*2^{m+1}-2*2^m-1=2*2^m-1$ ，我們可以找到類似的 $a_3$ .

由於 $a_1,a_2,a_3$ 必有兩個同奇偶（除以2^m之後），他們之和即可滿足條件。

------

更新1：此方法可以證明一個更強的結論，若n = pq且p,q滿足條件，那麼n也滿足。

證明：我們從2pq-1中可以選擇2p-1個q元集使得其和被q整除，最後再在其中選擇p個集合即可滿足條件。

不過n為素數的情況可能需要其他方法。

------

更新2： @YiZhou Liu證明了素數的情況，我剛才google了一下，這個定理被稱為：Erd?s-Ginzburg-Ziv定理，參見：http://www.renyi.hu/~p_erdos/1961-25.pdf 。他的證明也很初等。

補充：這裡：http://www.tau.ac.il/~nogaa/PDFS/egz1.pdf，有5個證明。。。