Archive for March, 2011

S04E18: The Prestidigitation Approximation

March 13, 2011

This week, Sheldon could not figure out Howard’s card trick using math.  But that was  fiction.  Playing cards and mathematics go hand in hand.  In real life,  Sheldon’s analysis may well have worked.

How many ways are there to shuffle a deck of cards?  This question is a classic example of a branch of mathematics called combinatorics.    The first card can be any, or 1 of 52 possibilities.  The second card is more constrained because one card has already been chosen.  So  it has 1 of 51 possibilities.   Now suppose you are asking what is the number of ways the first card is what it is AND that the second card is what it is.  In this case AND means multiply the possibilities, so there are 52*51=2,652 different ways to shuffle the first two cards.

Calculating for the rest of the deck is, the combinations are just 52*51*50*40*….*1.  The last card has no choice given that it is the only card left so is a factor of “1”.  Mathematicians have a shorthand for this result called 52!, or 52 factorial.  It is a number so large that even typing it into google won’t give all the digits, even though it is far less than a googol.   Instead you can find it on Sheldon’s board:

The number on Sheldon’s board. The number of ways to shuffle a deck of playing cards.

(The last 12 zeroes are not an approximation.  There are five tens in between 1 and 52.  And the five multiples of 5 always find a multiple of 2 to  give another five factors of ten.  Since 25 and 50 contribute two extra factors of 5 that find factors of 2, that is why there are 12 zeroes at the end.)

More compactly, this is 8*1067.  Or in plain English,  the number  is “80 unvigintillion”.  The British have a different word for it, “80 undecillion” but they don’t even get “a billion” right.  The Brits traditionally call a “trillion” a  “billion” because they skip over “billion” as a “thousand million”.  Since they don’t call a million a “thousand thousand”, consistency is apparently not their strong suit.

(To be fair, the UK switched from this so-called “long-scale”  naming convention to the “short scale” one used by the US and others in 1974, but the long scale persists in some countries.  And to think they scoff at Americans for not using the metric system.)

In any language it is still a large number.  Even if every one of the 7  billion men, women, and children on Earth played one billion card games every year for a billion years, they would not even make a dent in the number of possible shuffled decks of cards.

We may well ask a different question.  Has there likely ever been two games played from the same shuffled deck?  That is a different exercise in combinatorics.   The chance is much higher. The answer is not just the number of games ever played divided by that big number. An example of this effect is the classic question: “What is the chance that in a room of 23 people, two have the same birthday?”   You might naively guess 23/365 or 6%.   But it turns out to be greater than a 50% chance.   Among 57 people, there is a 99% chance that two have the same birthday.   Since twins sometimes hang out together and other correlations may be found,  the real chance  is much higher, but we are assuming everyone’s birthday in the room is independent.

If a 5o% chance seems surprisingly large for one pair among 23 people to have the same birthday, remember we haven’t chosen which day.   We are not asking the chance they have your birthday or Britney’s birthday, but that any pair has the same birthday, no matter what day.   Luckily, the same question can be asked a more illuminating, way:  What is the probability that nobody in the group has the same birthday as each another?   If there is 50% chance that none have the same birthday, then there is a 50% some pair does.

Phrased the second way, the odds are more easily calculated.  The first person has a no chance of matching on his own with anyone else.  The second still has 364 out of 365 chances of not matching.   The third has 363 chances in 365. And so on.   Multiplying these 23 factors:

(365/365)* (364/365)* (363/365)* (362/365)* (361/365)* (360/365)* (359/365)* (358/365)* (357/365)* (356/365)* (355/365)* (354/365)* (353/365)* (352/365)* (351/365)* (350/365)* (349/365)* (348/365)* (347/365)* (346/365)* (345/365)* (344/365)* (343/365)

= 0.49

That is a 49% chance no pair has the same birthday.  And hence, 51% do.

(The occasional presence of February 29, would not change our result much and I ignored the  five million people born on that day.)

So back to our problem of what is the chance that no two card games have ever started with the same deck.    I’ll start with assumption that every deck was well enough shuffled that they were all independent.  Given the number of drunk poker players and the fact that every purchased new deck starts out the same, I know this is a poor assumption.     Repeating the birthday calculation for decks of cards — using the big number above — is left for an exercise for the comments.

Martin Gardner wrote an article every month about “recreational mathematics” (Yes, there is such a thing) for the popular magazine Scientific American.    Mathematics of card tricks was an expertise of Gardner, just as Sheldon was reckoning on the white boards.  Many tricks were published in his 1956 book Mathematics, Magic and Mystery.   Here’s one of Martin Gardner’s simpler card tricks based on mathematics that  you can now use to amaze and entertain your friends for hours.

Martin Garnder wrote extensively about recreational mathematics, including the mathematics of card tricks. (photo: Colm Mulcahy in the New York Times)

Start with The Cyclic Number trick, which Gardner attributes to Mr. Lloyd Jones of Oakland California (1942).  Give your spectator five red cards: 2, 3, 4, 5, and 6.  Keep for yourself six black cards: A, 4, 2,8, 5, 7.  The magician deals out his cards in a row and has his spectator write down the number: 142857.  The player picks one of his cards, say 5, and multiplies the two on a sheet of paper giving in this case 714285.  The magician picks up his cards, gives a quick cut and lo and behold, deals out the six cards in order corresponding to the spectator’s multiplication: 714285.

The trick rests on the fact that the number 142857 is cyclic.  Multiply it by any number and the result will be the same numbers, in the same order.    What else would you expect the reciprocal of a prime number, in this case seven, to do?  Math (and a little dexterity faking the cuts and shuffles) is all you need.

Using the mathematical  structure of a deck (4 suits, 13 types of cards) leads to a variety of more complex games, including modular arithmetic which was the reason for “mod 4” and “mod 13” on the boards.   Pick up Gardner’s book and enjoy.

Sorry this blog post is late because I never did figure out the math behind Howard’s trick.