Prove for any number n, it is possible to select $X = 2^n$ numbers from $2^{n+1}$ numbers s.t. the sum of X is divisible by $2^n$

Question

Prove, for any natural number $n$, that it is possible to select $2^n$ numbers from any collection of $2^{n+1}$ natural numbers such that that sum of the $2^n$ numbers is divisible by $2^n$.

I am not sure how to even begin on this

Answer 1

HINT: Proceed by induction on $n$. For the induction step you’ll assume that if $A$ is a set of $2^{n+1}$ integers, there is a $B\subseteq A$ such that $|B|=2^n$, and $\sum B$ is divisible by $2^n$. Then let $A$ be a set of $2^{n+2}$ integers and try to show that there is a $B\subseteq A$ such that $|B|=2^{n+1}$, and $\sum B$ is divisible by $2^{n+1}$. To do this, consider two cases.

• If $A$ contains at least $2^{n+1}$ even numbers, let $A_0$ be a set of $2^{n+1}$ even elements of $A$, and apply the induction hypothesis to $\left\{\frac{a}2:a\in A_0\right\}$.

• Otherwise, let $A_0$ be a set of $2^{n+1}$ odd elements of $A$, and apply the induction hypothesis to $\left\{\frac{a-1}2:a\in A_0\right\}$.