Proving the Existence of a Subset with Divisible Sum in Number Theory

[AdrianZ]

Homework Statement

Suppose n is a natural number and A is a subset of natural number with n elements. Prove that a subset of A exists that the sum of its elements is dividable by n.

The Attempt at a Solution

well, This problem is harder than I can solve it. I first tried to use the pigeonhole principle to prove the existence of such a subset of A. well, It wasn't easy to prove it that way as I thought. so, now I feel that I'm stuck and have no idea of how to solve it. Any ideas?

 

[Robert1986]

You're on the right track with PHP. How many congruancy classes are there modulo n? Think about this for a bit, and I have another hint if you need one.

 

[AdrianZ]

You're on the right track with PHP. How many congruancy classes are there modulo n? Think about this for a bit, and I have another hint if you need one.

I've already thought about the number of congruency classes a lot. There are n congruency classes of modulo n ([0],...,[n-1]). In fact the Euclidean algorithm of division forces that. but the question is still so confusing. so another hint would be appreciated.

 

[Robert1986]

OK, let $a_1,a_2,\ldots,a_n$ be the elements of your n-element set. Consider these sums:

$a_1 \equiv m_1 mod n$
$a_1 + a_2 \equiv m_2 mod n$
$\vdots$
$a_1 + a_2 + \cdots + a_n \equiv m_n mod n$

Now, what would it mean if one of the $m_i$'s were 0? OK, now what if none of them are 0? How many congruancy classes does this leave? How many sums are there above? If a,b,c are integers and $a \equiv c mod n$ and $b \equiv c mod n$ what can you say about a-b mod n?

 

[AdrianZ]

OK, let $a_1,a_2,\ldots,a_n$ be the elements of your n-element set. Consider these sums:

$a_1 \equiv m_1 mod n$
$a_1 + a_2 \equiv m_2 mod n$
$\vdots$
$a_1 + a_2 + \cdots + a_n \equiv m_n mod n$

OK, now what if none of them are 0? How many congruancy classes does this leave?How many sums are there above? If a,b,c are integers and $a \equiv c mod n$ and $b \equiv c mod n$ what can you say about a-b mod n?

well, if one of them is zero, we're done. if none of them is zero, then we'll have n-1 congruency classes and n such sums. that would mean that two of these sums should be in the same congruency class. therefore if we subtract those two from each other we'll have a new sum that is congruent to 0 modulo n and we're done.

Thanks for the help.

 

[Robert1986]

Beautiful!