# West German Mathematics Olympiad 1981

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?

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