Wednesday, November 4, 2009

Wednesday Math, Vol. 95: The Kruskal Count

Depending on how far you got in your math education, you may have run across the last name Kruskal. In discrete math, one of the popular ways to solve the minimal spanning tree problem is called Kruskal's algorithm. In statistics, there's the Kruskal-Wallis test, a non-parametric method used for measuring the ranks of sub-groups of a set of data. Today's post is about the Kruskal count, a mathematical magic trick you can do with a deck of cards.

Here's the unusual thing. We have three different things named given the name Kruskal, and it's three different guys, all brothers. Joseph Kruskal, who worked at Bell Labs back in the 1950's, is given credit for Kruskal's algorithm, his brother William is the guy whose name adorns the Kruskal-Wallis test, and Martin Kruskal came up with the magic trick I'm about to discuss. Some might think Martin must have been the frivolous brother, but his more serious work is in mathematical physics, where he came up with the name "soliton" to describe the solitary wave because the wave has particle-like properties.

So here's the trick. You take an ordinary deck of cards, shuffle them up and ask a friend to pick a number between 1 and 10. Once your friend has chosen the number, you start dealing the deck out, one card at a time. Every number card is worth its face value, aces are worth 1 and face cards count 5. (More on "Why 5?" after the trick is explained.) Your friend counts the cards up to the number that was chosen, and the number on that card is the new number. Your friend again counts to a new card, and the number on that card is the new number, and the counting begins again. When the deck is finished, you will tell your friend what number they are thinking of at the end.

Let me give an example with the 25 shuffled cards in our picture. Your friend chooses 7 as the original number.

The seventh card is the six of spades. The new number is 6.
Six cards after that is the eight of diamonds. The new number is 8.
Eight cards after that is the eight of clubs. The new number is 8 and the next count will take us out of our first 25 cards.

The magic trick part is that you pick a number at random at the beginning. Let's say you pick 4.

The fourth card is the jack of hearts. The new count is 5.
Five cards after is the three of hearts. The new count is 3.
Three cards after that is the two of spades. The new count is 2.
Two cards later, the two of hearts. The new count remains 2.
Two cards later, the queen of diamonds. The new count is 5.
Five cards later, the eight of clubs.

You are now on the same card as your friend who started with 7, and your counts will be in sync for the rest of the deck, provided neither of you misses a count, so at the end, when you declare to your friend "Your count is x," it is because the count you came up with is x.

Here's the thing about the Kruskal Count. It doesn't work 100% of the time. About 63% of the time, a deck is shuffled in a way that you can't miss. No matter what number you choose and what number your friend chooses, you will both end up with the same count, barring errors in counting. As for the rest of the time when it isn't promised to agree, you can still get lucky, and the overall probability over all possible shuffles is around 86%.

The reason the numbers are this good (or this bad, depending on your point of view) is because Martin Kruskal decided that face cards should be worth 5. If instead face cards were worth 10, perfect deals would happen less than 50% of the time and the trick would work less than 80% of the time.

The thing is, the lower the value you give the face cards, the better the probability that the trick works. If you tell your friend that face cards count as 1, perfect deals happen 83% of the time and the overall probability of success is 94%. With face cards counting 2, the odds are about 80% perfect and 93% overall. With face cards at 3, we get about 73% perfection and 90% success rate overall.

When you do this trick, tell your friend face cards are worth 3 points. If you make it 1 point or 2 points, your friend may be able to see through the mathematical magic too easily. Tell them it's 3 points because there are three kinds of face cards. The trick will work more often this way. We'll call this the Kruskal-Hubbard Count. It'll be our little secret.

Technically, I'm never supposed to name something in math after myself, but this isn't really math, it's card tricks, right? I don't know if magicians have the same scruples about taking credit.

No comments: