MODBasic PigeonholePrinciple Intermediate

Problem - 4223

Show that from any given $m$ integers, it is always possible to select one or more integers such that their sum is a multiple of $m$.


Let these $m$ integers be $a_1$, $a_2$, $\cdots$, $a_m$. Then consider the following $m$ sums: $$\begin{array}{ll} S_1 &= a_1\\ S_2 &= a_1+a_2\\ S_3 &= a_1+a_2+a_3\\ &\cdots\\ S_m &= a_1 + a_2 + a_3 + \cdots + a_m \end{array}$$

If any of them is a multiple of $m$, the conclusion already holds. Otherwise, by the pigeonhole principle, at least two of them must have the same residue of modulo $m$. Hence, their difference, which is also a sum of some $a_i$, is a multiple of $m$.

report an error