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

[caffeinemachine]

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]

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]

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.