A lot of posts so far have been about interesting brain teasers that people have encountered during interviews. A cool site that contains a lot of these puzzles is William Wu’s “wu:riddles” page:
And the associated message board where almost all of the riddles are discussed and solved:
While solving some of these riddles, I came across one riddle that had a solution involving modular arithmetic:
This is a magic trick performed by two magicians, A and B, with one regular, shuffled deck of 52 cards. A asks a member of the audience to randomly select 5 cards out of a deck. The audience member — who we will refer to as C from here on — then hands the 5 cards back to magician A. After looking at the 5 cards, A picks one of the 5 cards and gives it back to C. A then arranges the other four cards in some way, and gives those 4 cards face down, in a neat pile, to B. B looks at these 4 cards and then determines what card is in C’s hand (the missing 5th card). How is this trick done?
As a concrete example, let’s take the perspective of magician A who has just been handed the following 5 cards from the audience member: and (w00t latex!). As a first observation, note that in any group of five cards, there are bound to be at least two cards of the same suit. So, adopt a convention where the first card in the pile sent to magician B matches the suit of the missing card. In our example above, the first card in the pile we send back will be a spade, indicating to magician B that the missing card is one of the twelve remaining spades.
However, magician B still doesn’t know which of the twelve remaining spades is the missing card. We have three more cards to add to the pile, and hence 3!=6 ways to do it. How do we describe twelve cards with only six possible orderings? The answer is modular arithmetic!
Assign values 1 thru 13 to the ranks Ace, 2, 3, …, K, respectively. Consider the ranks of the two cards that have the same suit. In modulo 13, it is always possible to add a number between 1 and 6 to one card to obtain the other. So, in the example above, we can pass back the first, and with the remaining three cards transmit the number 5, since .
The only problem that remains is coming up with a convention for representing the numbers between 1 and 6. If we induce an ordering on the deck, where Aces are low, Kings are high, and the suits are ordered from lowest to highest (alphabetically, like in Bridge), then we can order the three remaining cards as low (s), middle (m), and high (h). Then the convention can be:
So, in the example above, we would hand back the to indicate that the missing card is the !