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.

  • $\begingroup$ "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 $\endgroup$ – WaveX Oct 28 '19 at 15:59
  • $\begingroup$ @WaveX I edited for clarity. Incidentally, it isn't relevant that the values are non-negative. $\endgroup$ – Théophile Oct 28 '19 at 16:10
  • $\begingroup$ Induction is a good instinct on powers of two. What happens when you try it? $\endgroup$ – Théophile Oct 28 '19 at 16:13
  • 1
    $\begingroup$ 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$. $\endgroup$ – JMoravitz Oct 28 '19 at 19:21
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.