Is sum of numbered balls a multiple of a number?

Question

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

Answer 1

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$.

Answer 2

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?

Answer 3

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$.