Matt Parker released a video recently about a mind-bogglng card trick wherein he goes out of his way to introduce randomness into the shuffling of a deck of cards into two piles...and yet can make rock solid predictions about how many red cards and black cards are in each pile.
For those of you who did not watch the video, the goal is to come up with two piles of face-down cards of random length and random order. So go grab a standard deck of cards and do the following:
- Shuffle the cards good and proper
- Imagine you have two spots in front of you, the "Red Pile" and the "Black Pile"
- Flip over the first card and look at it, if it is red put the next card face down on the red pile and if it is black, vise versa. Put the face-up cards off to the side (you can use them to mark which pile is red and black, but really they don't matter)
- Proceed through the deck sorting every other card into the piles.
You should end up with half the deck face up and half the deck face down and sorted into two piles ("Red" and "Black"). You can go further and swap any number of cards, at random, between the two piles. The claim is that once you are done all of that the number of red cards in the first pile is equal to the number of black cards in the second pile.
At first glance this seems impossible. If the deck was well shuffled there should be no correlation between the colour of two subsequent cards, so it should be entirely random if a card was placed face down in one pile or another. The subsequent random swap also seems to guarantee that the two piles should be totally unrelated.
Except that the cards are related, at least if you are using a deck of cards with an equal number of black and red cards...
Let's imagine that you used a standard 52 card deck, suppose that after you shuffled you have flipped over $n$ red cards so the "Red Pile" has $n$ cards in it. This means there are $26-n$ cards in the "Black Pile" (since you flipped over every other card, 26 cards in total were flipped over). Suppose that there are $x$ red cards in the "Red Pile" and $y$ black cards in the "Black Pile". I put it all into a table.
|Red Pile||Black Pile|
I found after I wrote it out in a table it hit me immediately, and I felt stupid for not having seen it immediately.
The size of each pile tells you how many of each colour are left amongst the face down cards, because the size of each pile equals the number of coloured cards we removed from the deck. So if we put aside $n$ red cards to build a Red Pile of size $n$, we know there are $26-n$ red cards face down in the two piles in front of us (since there are 26 red cards in total).
But we also know there are only $26-n$ cards in the Black Pile, since our shuffling procedure divided the deck in half.
If there are $x$ red cards in the Red Pile then we know there are $26-n-x$ red cards left in the Black Pile. The Black Pile is of size $26-n$, so there must be $x$ black cards in the Black Pile as well.
The nice thing about this, is that it doesn't matter how you arrived at the those piles as long as there are $n$ cards in the Red Pile and $n$ red cards face up, everything else follows. All the obsession with shuffling and the bit about the dice are just a red-herring.