Splitting 1000 Coins Blindfolded Into Two Piles With Equal Heads
You are blindfolded and seated at a table with 1000 coins. You are told that exactly 20 of the coins are heads up and the remaining 980 are tails up, but the coins are mixed together and you cannot see or feel which side of any coin is facing up. You may move coins around and you may flip any coin over as many times as you like.
Divide the coins into two piles (of any sizes) so that both piles are guaranteed to contain the same number of heads-up coins. Describe your procedure and prove that it works.
Hints
- You cannot detect heads, so any procedure must work no matter how the 20 heads are distributed between the piles you form.
- Suppose you set aside a pile of $n$ coins that happens to contain $m$ heads. The other pile then has $20 - m$ heads. What does flipping every coin in the small pile do to its head count?
- Flipping all $n$ coins turns $m$ heads into $n - m$ heads. Choose $n = 20$ so that $n - m = 20 - m$ matches the other pile.
Worked Solution
How to Think About It: Since heads are undetectable, the only knobs you control are how many coins go into each pile and which coins you flip. Flipping a whole pile replaces "number of heads" by "number of tails" in that pile, and the pile size is something you know exactly. Combine that with the known total of 20 heads.
Approach: Set aside 20 coins, flip all of them.
Formal Solution:
*Step 1 -- Form the piles.* Take any 20 coins and put them in pile $A$. The remaining 980 coins form pile $B$.
*Step 2 -- Track the unknown.* Let $m$ be the (unknown) number of heads-up coins in pile $A$, with $0 \le m \le 20$. Since there are 20 heads in total, pile $B$ contains $20 - m$ heads.
*Step 3 -- Flip pile A.* Turn over every coin in pile $A$. Its $m$ heads become tails and its $20 - m$ tails become heads, so pile $A$ now has $20 - m$ heads.
*Step 4 -- Compare.* Pile $A$ has $20 - m$ heads and pile $B$ has $20 - m$ heads. They match for every possible value of $m$, so the guarantee holds regardless of how the heads were distributed.
*Step 5 -- General version.* With $N$ coins of which $h$ are heads, set aside any $h$ coins and flip them all; the piles then have equal heads. The total number of coins ($1000$ here) is irrelevant, only the number of heads matters.
Answer: Move any 20 coins into a separate pile and flip every coin in that pile. If that pile held $m$ heads before flipping, it holds $20 - m$ afterwards, exactly matching the $20 - m$ heads in the other pile.
Intuition
You cannot observe the heads, so you need a move whose effect is symmetric with respect to the unknown split. Flipping an entire pile of size $n$ maps its head count $m$ to $n - m$; if the pile has exactly as many coins as there are heads in total, that image is exactly the number of heads left in the other pile. The problem is a lesson in exploiting complementary counts: when you cannot measure a quantity, change the frame so that what you can control (the pile size) pins down what you cannot see. Similar complement tricks appear in inclusion-exclusion arguments and in constructing hedges whose payoff is determined by a total you know rather than components you do not.