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?

  • 1
    $\begingroup$ I don't have any useful insight to offer at the moment, but I can prove it true for $n \leq 3$. You could try solving the case $n=4$ and see if that gives you any clues about how to handle the problem in general. You could also think about whether there is a solution by induction on the exponent $k$. $\endgroup$ – Rupert Dec 8 '16 at 12:18

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.