Question

求证从任意的m个整数中必可选出若干个数,他们的和能够被m整除

Answer 1

设这m个整数为a[1],
a[2],...,
a[m].
记其中前k个数的和为S[k]
=
a[1]+a[2]+...+a[k],
并约定S[0]
=
0.
注意到S[k]除以m的
余数
只有0,
1,
2,...,
m-1这m种可能.
而k有0,
1,
2,...,
m共m+1种取值.
由
抽屉原理
,
存在0
≤
i
<
j
≤
m使S[i]与S[j]除以m的余数相同.
于是m
整除
S[j]-S[i]
=
a[i+1]+...+a[j].