排成一排的任何 n 个整数中，总能找到连续几个数之和是 n 的倍数

luyuanhong

[这个贴子最后由luyuanhong在 2009/08/26 00:15pm 第 1 次编辑]

elimqiu

[这个贴子最后由elimqiu在 2009/08/26 07:17pm 第 1 次编辑] 好题。证明可以简化如下： 令 Ai = a_i +...+a_n,  i=1,2,...,n 若 A1, A2, ..., An 中已有某项是n的倍数，断言已经成立，否则这n个数除以n的余数只能在 {1,2,...,n-1}中取值。由抽屉原则，必有整数j,m，1<= j < m <= n 使得 n | (Am - Aj) 命 k = m-1, 由此得 (a_j +...+a_k) = Sjk 为n的倍数。

luyuanhong

[这个贴子最后由luyuanhong在 2013/02/04 03:18pm 第 1 次编辑]

楼上 elimqiu 给出的证明很好，确实简单多了。