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!