This past weekend I attended the wedding of a former student, Jake Linenthal. On the dinner tables at the reception were sheets of paper containing a Mad Libs-style story of how Jake and his wife Abby got engaged, as well as a wedding riddle. The riddle went something like this:
An evil king has captured the bride and groom for a wedding that is about to take place. The king says that he will not let the wedding go on unless you can complete a task for him. First, he blindfolds you. Then he hands you a standard deck of 52 cards and tells you that 10 of the cards are face up and the rest are face down. Finally, he says that you have to divide the 52 cards into two stacks such that each stack has the same number of face-up cards. You cannot remove the blindfold, you cannot tell whether a card is face up or face down simply by touching it, and the cards are indestructible.
At first I could not see how it would be possible to complete such a task. There simply didn’t seem to be enough to work with here.
Then, after realizing that the rules do allow you to turn cards over, and working through an example where you have a deck of four cards with two of them face up, I found the solution.
Solution: Divide the deck into a stack of 42 cards and a stack of 10 cards. Then turn over every card in the 10-card stack.
Why does this work? You know that 10 cards are face up. Suppose x of the face-up cards are in the stack of 42 cards. That means that the stack of 10 cards has cards that are face up and x cards that are face down. Turning over every card in the 10-card stack then gives you cards that are face down and x cards that are face up. With x face-up cards in the 42-card stack and x face-up cards in the 10-card stack, you’ve completed the king’s task and saved the wedding.
The form of the solution means that we can easily generalize the problem. Suppose you have an n-card deck in which m cards are face up, and you have to divide all the cards into two stacks with the same number of face-up cards in each. Then the solution is to (1) Divide the cards into a stack of cards and a stack of m cards, and then (2) Turn over every card in the stack of m cards.
Interestingly enough, with this solution you won’t know how many face-up cards are in each stack. But, fortunately, the task doesn’t require that.