## Divisible by 100

Posted on: July 29th, 2013 by
1

Given any 100 integers, show that one can find a subset of these 100 integers whose sum is divisible by 100.

Let $S_1 = a_1$, $S_2 = a_1 + a_2$ and so on be the partial sums of the numbers given. If all $S_i$, $i=1,\dots,100$ leave distinct reminders modulo 100, we are done since 0 should be in there somewhere. If not, there should be two indices $i,j$ such that $S_i \equiv S_j mod 100$ which means that the subset $a_{i+1},\dots,a_j$ has sum divisible by 100.