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