Number Theory/Combinatorics question:
I had an interesting question in an assignment I had recently which I thought you guys would like to have a go at:
"Let $S$ be a set of $n$ pair-wise distinct positive integers. Prove
that there exists a subset $T$ in $S$, such that the sum of elements in $T$ is
divisible by $n$."

For example, suppose we have 5 numbers:
$${3, 6, 11, 8, 7} $$
Then we have 7+3=10 which is divisible by 5.

Question

Number Theory/Combinatorics question:
I had an interesting question in an assignment I had recently which I thought you guys would like to have a go at:
"Let $S$ be a set of $n$ pair-wise distinct positive integers. Prove
that there exists a subset $T$ in $S$, such that the sum of elements in $T$ is
divisible by $n$."

For example, suppose we have 5 numbers:
$${3, 6, 11, 8, 7} $$
Then we have 7+3=10 which is divisible by 5.

anonymous · Answer

Let some be the eyes breaker............

anonymous · Answer

There's a few proofs, I did a proof by disproving that it's possible to create a set which doesn't have this property. I've seen one which is focused around the injectivity of functions though.

anonymous · Answer

Let S={a1,a2,a3,...an}
Then,
S={x1*n+c1 ,x2*n+c2 , x3*n+c3+...xn*n+cn} where x>= 0 Then, c1,c2,c3...cn must be less than n.......

anonymous · Answer

Great idea.

anonymous · Answer

What do you mean by x1*n @sauravshakya ?

anonymous · Answer

|dw:1349192961820:dw|

anonymous · Answer

and what are these $c_1,...c_n$?

anonymous · Answer

That are natural numbers that must be less than n

anonymous · Answer

Oh are you just preparing to do some modular arithmetic?

anonymous · Answer

For example: |dw:1349193058867:dw|