I have 11 dalmatians. Can I find a subset of these 11 dalmatians such that the sum of the number of spots they have is divisible by 11?
My thoughts are that if there exist 1 dalmatian that has spots divisible by 11, then we find our subset (just take that dalmatian); On the other hand, if there does not exist such dalmatian, we could count the number of spots on each dalmatian and divided by 11, then we could get remainders from 1 to 10. We then put each dalmatian to the 10 bins according to the remainders calculated before.
Then by pigeon-hole principle, there is at least one bin that has at least 2 dalmatians. I am not sure how to proceed from here to solve the problem. I feel like I am missing some key pieces. Any help is appreciated!
HINT: Let $s_1,s_2,\ldots,s_{11}$ be the numbers of spots on the Dalmatians. For $k=1,\ldots,11$ let $t_k=s_1+\ldots+s_k$, the total number of spots on the first $k$ Dalmatians. Now apply your pigeonhole argument to the numbers $t_1,\ldots,t_{11}$. If one of them is divisible by $11$, you’re done. If $t_k$ and $t_\ell$ have the same remainder on division by $11$, where $k<\ell$, can you find a set of Dalmatians that collectively have a number of spots divisible by $11$?