證明:在任意 15個整數中,必有8個整數的和是8的倍數?
01-07
RT或者能否推廣到任意2n-1個整數中,必有n個整數的和是n的倍數
3 2 2 5 3 3都比較好推出,9 5 5開始就混亂了。哎 感覺沒有把握好抽屜原理的精髓orz
歸納法:我們證明對任意,在任意
個數中必有
個數之和被
整除。
再進一步,我們可以找到類似的
.
由於必有兩個同奇偶(除以2^m之後),他們之和即可滿足條件。
不過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個證明。。。推薦閱讀:
※一些初等函數如e^x^2之原函數不存在應如何證明?是否有系統的理論用以解決類似的函數原函數不存在的證明?
※等號上面有一個三角是什麼運算符?
※隨機變數除了離散型和連續型還有什麼類型?
※求推薦適合自學的複分析教材(學過複變函數)?
※九個 1~9 的數,使其和為 45、積為 362880 的方案有幾種?如何證明?