If $n=2^k$ then from a set of $2n-1$ elements we can select $n$ numbers such that their sum is divisible by $n$.
I divided it in two case, first if any $n$ of them have the same remainder mod $n$ the we are done, in the other case i am having difficulty.
What if $n$ is any natural number?
Answer
Induction on $k$:
The claims is clear for $n=2^0$.
Let $k>0$, assume the claim holds for $n'=2^{k-1}$ and let $S$ be a set of $2n-1$ integers.
By induction hypothesis, we can pick $n'$ numbers from the first $2n'-1$ elements of $S$, such that their sum is a multiple of $n'$.
After removing these from $S$, we still have $2n-1-n'=3n'-1$, so from the first $2n'-1$ of these, we can again pick $n'$ such that their sum is a multiple of $n'$. After removing these as well, we are left with $2n-1-2n'=2n'-1$ numbers and again we can pick $n'$ elements such that their sum is a multiple of $n'$.
So now we have three disjoint subsets of $S$ of size $n'$ each and such that each sums to a multiple of $n'$. Note that a multiple of $n'$ is either a multiple of $n$ or an odd multiple of $n'$; one of these two types must occur at least twice among our three subsets. By combining two such like subsets, we arrive at a set of size $n$ with sum a multiple of $n$.
No comments:
Post a Comment