# Use Pigeonhole to show of any set of $2^{n+1}-1$ positive integers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

Show that, of any set of $2^{n+1}-1$ positive integers numbers is possible choose $2^{n}$ elements such that their sum is divisible by $2^{n}$.

My approach: Let $a_1,a_2,\ldots,a_{2^{n+1}-1}$ positive integers numbers. Define, $s_j=a_1+a_2+a_3+\ldots+a_{2^{j+1}-1}$, $j\in\{1,\ldots,n\}$.

If any of the $2^{n+1}-1$, $s_j$, are divisible by $2^n$, we are done.

In case contrary, $s_j$ have a remainder $1,2,3,\ldots,2^{n}-1\mod(2^n)$. And, we know that $2^{n+1}-1>2^n-1$, so by Pigeonhole Principle, there exist a tleast two $s_j$ such that has a same remainder ($\mod(2^n)$), i.e., if $p<q$, then $$s_q-s_p=a_{2^{p+1}}+a_{2^{p+1}+1}+\ldots+a_{2^{q+1}-2}+a_{2^{q+1}-1}\equiv 0\mod(2^{n})$$

So, the set $\{a_{2^{p+1}},a_{2^{p+1}+1},\ldots,a_{2^{q+1}-2},a_{2^{q+1}-1}\}$ is the set we need. I know, this answer doesn't be right, but is the idea I have to occupy Pigeonhole.

EDIT: Both answers were very good, but, how I could occupy the pigeonhole principle in this problem?

• Do they have to be distinct elements in the sum? – Andrew Whelan Jul 24 '16 at 1:33
• @Andrew it'd be pretty easy if not. You could just pick the same element $2^n$ times. – Matt Samuel Jul 24 '16 at 1:39
• I think he means if it is possible to repeat an element more than once. – Jorge Fernández Hidalgo Jul 24 '16 at 1:39
• @AndrewWhelan In the problem doesn't says nothing about it. So, I suppose should to be distinct elements. – MathUser Jul 24 '16 at 1:40
• I added an answer explaining the precise relation to EGZ. One can recycle the easier part of the EGZ proof to solve this. @user4759923 – zyx Jul 24 '16 at 2:36

We proceed via induction over $n$.

The base case is $n=1$ and it is trivial, we have $3$ numbers, so clearly we can pick two with the same parity.

Inductive step:

Split the $2^{n+1}-1$ elements into two groups of size $2^{n}-1$ and an extra element.

By the inductive hypothesis we can pick two groups of $2^{n-1}$ elements from each group, with sum divisible by $2^{n-1}$. If these sums are congruent $\bmod 2^{n}$ we are done (just take the union).

Otherwise notice we have $2^{n+1}-1-2^{n-1}-2^{n-1}=2^n-1$ elements that are in none of the two groups. So by the inductive hypothesis we can form a third group of $2^{n-1}$ elements with sum divisible by $2^{n-1}$. This sum must be congruent $\bmod 2^n$ to one of the other two groups.

• It can be slightly reworded, if we have $2^n-1$ elements we can extract a subset of $2^{n-1}$ elements with sum divisible by $2^{n-1}$. We can use this to extract three disjoint subsets of size $2^{n-1}$ and sum which is either $0$ or $2^{n-1}\bmod 2^n$. Take two which are congruent $\bmod 2^n$, their union does the trick. – Jorge Fernández Hidalgo Jul 24 '16 at 1:58
• Very nice answer, but I have a confusion with your last phrase "This sum must be congruent $mod(2^{n})$ to one of the other two groups". Thanks again for your answer! – MathUser Jul 25 '16 at 3:17
• Yeah, we have three groups. They are $A,B$ and $C$. Each of them has a sum that is either $0$ or $2^{n-1}\bmod 2^n$. So there are two groups that are congruent $\bmod 2^n$. Their union is the set we need. – Jorge Fernández Hidalgo Jul 25 '16 at 3:23

As suggested in the comments this is Erdos-Ginzburg-Ziv theorem for a power of $2$.

The proof of E-G-Z has an easy inductive part, that if the theorem is true for $p$ and $q$ it is true for $pq$, and a nontrivial base case of proving the theorem true for primes. Here the prime is $2$ so the base case is true by inspection. The proof of the multiplicative property is the same whether or not $p=q$ or if they are powers of $2$.

https://en.wikipedia.org/wiki/Zero-sum_problem

• Thanks for your answer!, but exist other method for prove this?? I think the pigeonhole principle is enough. – MathUser Jul 26 '16 at 0:18