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.
Answer
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.
No comments:
Post a Comment