# Prove that he can bring back this amount of coins

there are $$2^{n+1}$$ coins ($$n$$ is a natural number). Each coin has a non-negative integer value. The coins are not necessarily distinct. Prove that it is possible to bring exactly $$2^n$$ coins such that the total value of earnings is divisible by $$2^n$$.

My thoughts: So you can only bring back half of the coins, so I think we need to prove this somehow by induction or pigeonhole principle?

With induction on $$n$$. Base case: $$n=0$$, so there are $$2$$ coins total and can only bring back $$1$$ coin. Any natural number is divisible by $$2^0=1$$ so base case holds.

IH: Assume claim holds true for $$n=k$$.

IStep: Prove claim holds true for $$n=k+1$$. So there are $$2\cdot{2^{k+1}}$$ coins. We can split this up using algebra: $$2^{k+1}+2^{k+1}$$ Consider any of the $$2^{k+1}$$ coins. By IH, we can bring $$2^{k}$$ coins back that fits the claim.

• "Each coin is of value greater than or equal to $0$ that is an integer" - could you explain this part a little more? It seems a little vague to me – WaveX Oct 28 '19 at 15:59
• @WaveX I edited for clarity. Incidentally, it isn't relevant that the values are non-negative. – Théophile Oct 28 '19 at 16:10
• Induction is a good instinct on powers of two. What happens when you try it? – Théophile Oct 28 '19 at 16:13
• In your attempt you found a fourth of the coins whose sum is divisible by a fourth of the number of coins. We were asked to find half of the coins whose sum is divisible by half of the number of coins. You stopped just a bit too soon. Be careful though. $24$ is divisible by $2$ and so is $26$, but $24+26$ is not divisible by $4$. – JMoravitz Oct 28 '19 at 19:21
• @hardmath I agree with your suggestion that a simpler argument can be used here instead. Thus, I've undeleted my answer (after adding more details based on my comment above), including a link to the other question & the paper. Also, I've retracted my vote to close as a duplicate. – John Omielan Oct 28 '19 at 23:48

You have already handled the base case of $$n = 0$$. Next, assume it's true for $$n = k$$ for some integer $$k \ge 0$$, i.e., among any $$2^{k+1}$$ coins, there are $$2^{k}$$ coins which sum to a multiple of $$2^k$$.

With $$n = k + 1$$, consider the $$2^{k+2}$$ coins. From the assumption for $$n = k$$, since $$2^{k+2} \gt 2^{k+1}$$, there are $$2^{k}$$ coins which sum to a multiple of $$2^{k}$$, say $$a\left(2^{k}\right)$$. Remove those coins, leaving $$3\left(2^{k}\right)$$. As this is still $$\gt 2^{k+1}$$, there are another $$2^{k}$$ coins which sum to a multiple of $$2^{k}$$, say $$b\left(2^{k}\right)$$. Once again, remove those coins, leaving $$2^{k+1}$$ coins remaining. For one more time, there are $$2^k$$ coins among these which sum to a multiple of $$2^k$$, say $$c\left(2^{k}\right)$$. Remove these set of coins again.

There are now $$3$$ sets of $$2^{k}$$ coins, with sums of $$a\left(2^{k}\right)$$, $$b\left(2^{k}\right)$$ and $$c\left(2^{k}\right)$$. Now, among $$a$$, $$b$$ and $$c$$, since there are only $$2$$ parity values (i.e., even or odd) but $$3$$ values, by the Pigeonhole principle, there are at least $$2$$ which have the same parity, i.e., they are both even or both odd. WLOG, say these are $$a$$ and $$b$$, so $$a + b$$ is even, meaning $$a\left(2^{k}\right) + b\left(2^{k}\right) = (a + b)2^{k}$$ has a factor of $$2^{k+1}$$. As this comes from $$2^{k} + 2^{k} = 2^{k+1}$$ coins, this means the question is true for $$n = k + 1$$ as well, finishing the induction procedure.

In summary, this proves that among any $$2^{n+1}$$ coins, for an integer $$n \ge 0$$, there are $$2^{n}$$ which sum to a multiple of $$2^{n}$$. Note this doesn't use, or need, that the coin values are non-negative, but only that they are integral.

Also, there's a more general question, with an answer, at Show that in any set of $$2n$$ integers, there is a subset of $$n$$ integers whose sum is divisible by $$n$$.. The answer's comment has a link to the original paper of Erdős, Ginzburg and Ziv. In this paper, the latter part shows how to prove the more restrictive requirement of there being among $$2n - 1$$ integers a subset of $$n$$ integers with a sum divisible by $$n$$ is true for $$n = u$$ and $$n = v$$, then it's also true for $$n = uv$$. Note I use a variation of this idea in my proof above.