# Among 2n-1 integers summation of some n of these is divisible by n.

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Let $k$ be a positive integer. Let $n=2^{k-1}$. Prove that, from $2n-1$ positive integers, one can select $n$ integers, such that their sum is divisible by $n$.

#### CaptainBlack

##### Well-known member
Let $k$ be a positive integer. Let $n=2^{k-1}$. Prove that, from $2n-1$ positive integers, one can select $n$ integers, such that their sum is divisible by $n$.

Suppose this true for some $$k$$.

Now consider the case for $$k+1$$, then $$n_{k+1}=2n_k$$ and any set of $$2n_{k+1}-1$$ positive integers. Now split the $$2n_{k+1}-1$$ positive integers into three sets two of size $$2n_k-1$$, and one of size $$1$$.

We can select $$n_k$$ integers from the first set with sum divisible by $$n_k$$, and a set of $$n_k$$ integers from the second set with sum divisible by $$n_k$$. So we have a combined set of $$2n_k=n_{k+1}$$ integers from the set of 2n_{k+1}-1 integers with sum equal to 2n_k=n_{k+1}.

The rest of the details for a proof by induction I leave to the reader.

CB

#### caffeinemachine

##### Well-known member
MHB Math Scholar
Suppose this true for some $$k$$.
We can select $$n_k$$ integers from the first set with sum divisible by $$n_k$$, and a set of $$n_k$$ integers from the second set with sum divisible by $$n_k$$. So we have a combined set of $$2n_k=n_{k+1}$$ integers from the set of $2n_{k+1}-1$ integers with sum equal to $2n_k=n_{k+1}$.
I think "equal to" is a typo. What you probably intended was "divisible by". But even that is not guaranteed (at least I am not convinced). Divisibility by $n_k$ is guaranteed though.