Is sum of numbered balls a multiple of a number? would you please help me with this problem?
We have an urn with n balls numbered such that $X_i$ is the value of the ith ball, and we're asked to draw $k$ balls from the urn and then prove that their sum can be a multiple of $n$. Working on this problem, the furthest I got to is expecting the sum of the chosen balls which is $S= k (n+1) /2$ but I have no idea how to prove that we can obtain a multiple of $n$ by drawing some $k$ balls. 
Any help please? Thanks
 A: Even if you don't know the numbers written on the balls, you can still solve the problem by counting:


*

*When you divide a number $m$ by $n$, the remainder can be anything in the list $0,1,2,\ldots, (n-1)$. If the remainder is 0, then $m$ is a multiple of $n$.

*Consider the sums you can make by adding up the values of the first few balls in order: $X_1$, $X_1+X_2$, $X_1+X_2+X_3$, and so on. Let $S_k$ be the sum of the first $k$ balls.

*We're considering $n$ different sums $S_1, \ldots, S_n$. 

*When we divide those sums by $n$, we'll get $n$ remainders in the range $0\ldots (n-1)$.  If one of those remainders is zero, our proof is finished.

*Otherwise, all of the remainders are in the range $1,2,3,\ldots, (n-1)$, leaving zero out.  So by the pigeonhole principle, there are $n$ remainders chosen from the range of $n-1$ different numbers: $1,2,3,\ldots,(n-1)$. So two of these sums have the same remainder.

*Because two of them have the same remainder, $S_i$ and $S_j$, their difference is a multiple of $n$. (You can prove this because if $S_i = an + c$ and $S_j = bn+c$, then $S_i-S_j = (a-b)n$.)

*Their difference is $(X_1+\ldots+X_i) - (X_1+\ldots+X_j) = (X_{j+1}\ldots X_i).$  So this is a subset of balls that adds up to a multiple of $n$.
A: HINT: 
Consider the sums $$S_k = \sum_{i=1}^k{X_i}.$$  Apply the pigeonhole principle.  
EDIT:
I see you've added a comment that you already had this hint.  Okay, since we are only concerned with divisibility by $n,$ only the remainder on division by $n$ matters.  If one of these sums leaves a remainder of $0,$ we're done, so the only possible remainders are $1,2,3,\dots,n-1.$
Now the pigeonhole principle tells you that two of the sums have the same remainder.  Can you finish it?   
A: Consider the subsets $\{X_1\}, \{X_1, X_2\}, ... \{X_1, X_2, .. X_n\}$
We have $n$ sets. Either one of them will be a multiple or some two will have the same remainder mod $n$
Hence their difference is $0 \ mod\  n$. If the sets are from $X_1$ to $X_k$ and $X_1$ to $X_m$, then the set $X_{k+1}$ to $X_m$ will have a sum that is a multiple of $n$. 
