Combinatorics and number theory

**james_bond** · December 25th 2008, 12:09 AM

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?

**awkward** · December 26th 2008, 12:40 PM

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 $x_1, x_2, \dots , x_{10}$ . Consider the sums $s_n = \sum_{i=1}^{10} x_i$ for $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 $s_j$ and $s_k$ , with $j < k$ , have the same remainder, by the Pigeonhole Principle. Then $\sum_{i=j+1}^k x_i$ is divisible by 10.

**Grandad** · December 27th 2008, 02:39 AM

Originally Posted by awkward

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

Should this be:

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

Grandad

**awkward** · December 27th 2008, 05:27 AM

Originally Posted by Grandad

Should this be:

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

Grandad

Grandad,

Yes, that was the idea but I didn't get it typed in right.

Thanks for the correction.

Awkward

Thread: Combinatorics and number theory

LinkBack

Thread Tools

Display

Combinatorics and number theory

Similar Math Help Forum Discussions

Textbooks on Galois Theory and Algebraic Number Theory

Applied combinatorics: graph theory non-isomorphic trees help please?

Combinatorics using the number of conjugate subgroups

Find the number of intersection points?(Combinatorics)

Number Theory type of problem--need help understanding number relationships. yikes.

Search Tags