# Combinatorics and number theory

• Dec 25th 2008, 12:09 AM
james_bond
Combinatorics and number theory
10 integers are given. We know that there is no way of choosing some of them whose sum is divisible by 10. What can be the remainders of the 10 integers when divided by 10?
• Dec 26th 2008, 12:40 PM
awkward
Quote:

Originally Posted by james_bond
10 integers are given. We know that there is no way of choosing some of them whose sum is divisible by 10. What can be the remainders of the 10 integers when divided by 10?

Hi james bond,

No such collection of integers can exist.

Let's say the integers are $\displaystyle x_1, x_2, \dots , x_{10}$. Consider the sums $\displaystyle s_n = \sum_{i=1}^{10} x_i$ for $\displaystyle n = 1, 2, \dots , 10$. If any of the sums is divisible by 10 we're done, so let's suppose none of them are. Then the possible remainders of the sums are 1, 2, ..., 9. Since there are 10 sums and 9 possible remainders, at least two of the sums, say $\displaystyle s_j$ and $\displaystyle s_k$, with $\displaystyle j < k$, have the same remainder, by the Pigeonhole Principle. Then $\displaystyle \sum_{i=j+1}^k x_i$ is divisible by 10.
• Dec 27th 2008, 02:39 AM
Quote:

Originally Posted by awkward
Consider the sums $\displaystyle s_n = \sum_{i=1}^{10} x_i$ for $\displaystyle n = 1, 2, \dots , 10$.

Should this be:

$\displaystyle s_n = \sum_{i=1}^{n} x_i$ for $\displaystyle n = 1, 2, \dots , 10$?

• Dec 27th 2008, 05:27 AM
awkward
Quote:

$\displaystyle s_n = \sum_{i=1}^{n} x_i$ for $\displaystyle n = 1, 2, \dots , 10$?