# 10 naturals numbers.

• Dec 8th 2009, 10:58 AM
Also sprach Zarathustra
10 naturals numbers.
Let be a group wit 10 naturals numbers.

1. Is there a non-empty subset that the sum of element divides by 10?

2. Is there a non-empty subset that the sum of elements divides by 11?
• Dec 8th 2009, 02:06 PM
awkward
Quote:

Originally Posted by Also sprach Zarathustra
Let be a group wit 10 naturals numbers.

1. Is there a non-empty subset that the sum of element divides by 10?

2. Is there a non-empty subset that the sum of elements divides by 11?

1. Hint:

Suppose the numbers are $x_1, x_2, x_3, \dots , x_{10}$.

Consider the 10 sums

$\sum_{i=1}^j x_i$ for j = 1, 2, 3, ...., 10.

If one of these sums is congruent to 0 mod 10 we are done. If not, all the sums must fall in the congruence classes 1, 2, 3, ... 9 mod 10. Since there are 10 sums and only 9 congruence classes, at least two of the sums must be in the same class. Then...