Posted by: rfgarcia | October 30, 2008

Modular Arithmetic and A Cool Card Trick

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:

http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml

And the associated message board where almost all of the riddles are discussed and solved:

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi

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?

Solution

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: $10\spadesuit, Q\heartsuit, 8\clubsuit, 3\diamondsuit$ and $2\spadesuit$ (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 $10\spadesuit$ first, and with the remaining three cards transmit the number 5, since $10+5\equiv\mbox{2 (mod 13)}$.

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 $\clubsuit\diamondsuit\heartsuit\spadesuit$ (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:

$\begin{array}{rcl} \{l,m,h\} &=& 1 \\ \{l,h,m\} &=& 2 \\ \{m,l,h\} &=& 3 \\ \{m,h,l\} &=& 4 \\ \{h,l,m\} &=& 5 \\ \{h,m,l\} &=& 6 \end{array}$

So, in the example above, we would hand back the $10\spadesuit, Q\heartsuit, 3\diamondsuit, 8\clubsuit$ to indicate that the missing card is the $2\spadesuit$!

Responses

1. Wonderful card trick! It’s an interesting question, isn’t it… just how much information can you convey by removing one card and reordering the others? In this case, plenty.

2. There are 5 houses in five different colors
In each house lives a different nationality.
These 5 owners drink a certain beverage, smoke a certain brand of cigar and keep a certain pet.
No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

The CLUES:

The Brit lives in the Red house.
The Swede keeps dogs as pets.
The Dane Drinks tea.
The Green House is on the left of the White House.
The Green House’s owner drinks coffee.
The person who smokes Pall Mall rears birds.
The owner of the yellow house smokes Dunhill.
The man in the center house drinks milk.
The Norwegian lives in the first house.
The man who smokes Blends lives next to the one who keeps cats
The man who keeps horses lives next to the man who smokes Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Norwegian lives next to the Blue House.
The man who smokes Blends has a neighbor who drinks water.
The QUESTION:

Who owns the fish?

3. I believe its house 1, Norwegian, water, Dunhill, Fish!!

4. Great puzzle. I really suggest doing it! The answer: House 1 – yellow: The Norwegian, cats, water, Dunhill; House2 -Blue: The Dane, horses, tea, Blends; House3 – red: The Brit, birds, milk, Pall Mall; House4 – green: The German, fish, coffe, Prince; House5 – white: The Swede, dogs, beer, Blue Master.

5. Oh my goodness! Awesome article dude! Thank you, However
I am encountering troubles with your RSS. I don’t know the reason why I am unable to join it.
Is there anybody having identical RSS problems?
Anyone who knows the answer can you kindly respond?
Thanks!!

6. Aside from being an excellent review site, Flixster is slowly but steadily starting to add more movies,
TV shows, and video clips to the site. The same is likely true for totally colour blind individuals.

The other advantage of watching Nollywood movies online is the
fact that you also don’t need to worry about such issues as whether the movie
will be ruined in time.