S04E18: The Prestidigitation Approximation

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.

39 Responses to “S04E18: The Prestidigitation Approximation”

  1. Randal L. Schwartz Says:

    The idea of Howard pre-arranging to have everyone in as stooges just to get Sheldon mad is priceless! Admittedly, I didn’t get it until the lunchroom trick, but I’m glad that reveal was there.

  2. Indrek Says:

    Actually, the Brits use the word “billion” for 10^9, just like the Americans, and have been doing so since 1974. Also, in most countries where “billion” does mean 10^12, the word for 10^9 is not “thousand million”, which unarguably is quite a silly term, but “milliard”.

    Finally, there’s no other word for 10^68 in English. Since in long scale (the system your comment about the Brits was actually aimed at) each new term greater than 10^18 is 10^6 times larger than the previous (not 10^3 like in short scale), the closest term would be “undecillion”, which is 10^66. So the number of ways to shuffle a deck of cards would be called “eight hundred undecillions”.

    • Indrek Says:

      Actually, there’s no word for 10^68 in English. “Unvigintillion” is actually 10^66.

      Further, 52! = 8 * 10^67.

      • David Saltzberg Says:

        Indeed I was off by a factor of 10 for 52 factorial. Thank you, I have fixed it and the name of the number. As for what the British traditionally called large numbers, I took that from wikipedia here: http://en.wikipedia.org/wiki/Names_of_large_numbers . They say “thousand million” is traditional British for billion whereas “millard” is continental European. The number name I use, “80 unvigintillion” is in the column for US and modern British. I’ve added a link to long and short scales for the interested reader. While the British have made the change to short scale, it is not universal. See http://en.wikipedia.org/wiki/Long_and_short_scales#Long_scale_countries .

      • Indrek Says:

        Fair enough. Though if you look at the table in the “Names of large numbers” article you link to, you’ll see that the traditional British method is actually perfectly consistent. It uses the exact same terms as the US method, but simply spaces them out a bit more (hence “long scale”) – every sixth power of ten is a new term with the -illion suffix, and every third power of ten between those is prefixed with “thousand”. The continental European method is only slightly different by changing the -illion suffix to -illiard instead.

        A million isn’t called “thousand thousand” because there’s no need – the word “million” already exists. And “billion” isn’t skipped over, it’s simply the next term after “thousand million”. Even if it seems a bit confusing at first, this is nowhere as big of a mess as the imperial system where the relations between different units are pretty much arbitrary.

      • Braden Says:

        Yeah, I think you’re unfairly dismissive of the long scale–if anything, it’s simpler to use 10^(6n) than 10^(3(n+1)).

      • David Saltzberg Says:

        Why do you add +1? The short scale just counts factors of 10^3, with the first one being thousands, the next being millions etc. The long scale has the extra complication of not just 10^6 counts for word increments but also with epicycles of 10^3 within it.

      • David Saltzberg Says:

        OK, I get the +1 now based on the comments…it is because the prefixes have meaning. I buy it. Perhaps someone should start a facebook campaign to go back to the long scale.

      • feldfrei Says:

        Regarding the beauty of epicycles this reminds me the “double-bay system” in romanesque architecture where each vaulted bay in the nave corresponds to two vaulted bays in the aisles: http://en.wikipedia.org/wiki/Speyer_Cathedral
        But that’ now a matter of aesthetics – I just like the long scale building more. Those who prefer the short scale seem to be fans of the gothic style ;-)

      • feldfrei Says:

        Short addendum: the +1 is obvious. A million in the short scale is 1000^(1+1), a billion 1000^(2+1), a trillion 1000^(3+1) …

      • David Saltzberg Says:

        Oh, I see…for counting prefixes. True that.

      • Bas de Heer Says:

        The way continental europeans use million and billion and trillions is actually quite logical and nullifies the usage of unvigtillion etc…
        They are multiples of 10^6. Mono is one. (Methyl for example), Bi is too, so Billion, Tri = 3 (Trillion)

        We also use milliard and billiard and trilliard in between the *ions ;-)

    • feldfrei Says:

      The logic behind the long scale is simple – it just counts the powers of a million (10^6) which is the first term named -llion. Thus, a million squared is a bi-llion, third power a tri-llion and so forth. Based on this logic, it’s a matter of taste whether you like the “thousand” prefix or the -lliard suffix. My taste favours -lliard – but that may be a cultural bias. An advantage of the long scale is that it’s use of names is a factor two (on the log scale) more economic.

      • David Saltzberg Says:

        Both scales take an infinite number of words to label all numbers, so what’s the economy in saving a factor of two.

      • feldfrei Says:

        You are right, that a factor two is not of that interest regarding infinity. But in practice, we deal with finite quantities and then in many cases the factor two helps. The Planck time unit for instance is just about 20 septillion times shorter than a second – in the long scale, which I find quite convenient. ‘course the scientific notation 10^n has no problem with that at all :-)

  3. tudza Says:

    Sheldon’s analysis was flawed. One look at a library book or even a search on magic would have allowed him to figure out the trick. I know I figured it out first time.

    I did enjoy his own try at replicating the trick though. A little more work on it and he might have had them fooled.

    • Michel S. Says:

      Then again, considering Sheldon is really bad at both lying and acting, he probably could not have fooled them anyway.

      There’s a typo in Garner’s Cyclic Number trick — “Give your spectator six red cards: 2, 3, 4, 5, and 6.” — that’s 5 cards!

  4. Michael Says:

    Yes, clearly any convention which isn’t American must be “wrong” and therefore logically flawed! But good for the “Brits” eh, they eventually saw sense. Perhaps one day they’ll start driving on the right and stop misspelling the word colour and calling soccer football!

  5. Martin Says:

    There are only 5 tens between 1 and 52 and 5 multiples of 5 that are not tens. But 25 and 50 each provide an additional factor 5.

  6. Brian Says:

    Regarding the last trick, when Sheldon drew the 2 of hearts: this might have been a “goof” instigated by multiple shoots of the scene, but when Howard dumps the cards out of the deck, you can see (briefly) that the bottom card of the deck was the 2 of hearts. (Impossible assuming a continuous sequence to the shot when Sheldon draws the card, unless either Howard actually did perform a slight of hand in either spreading out the cards or when he moves the spread-out cards closer to Sheldon, or, of course, unless every card in the deck was a 2 of hearts.) (There was no shuffling involved, so this couldn’t have been random chance.)

  7. Nick Says:

    > (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.)

    Yeah, those crazy brits for scoffing at the non-use of the metric system when they have only been using the international terminology for the last 36 years! And clearly the way america does stuff is the only “correct” way to do things – others don’t even get “a billlion” correct.

    Pretty disgusting.

  8. Arturo Quirantes Sierra Says:

    “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.”

    Says who? I don´t see any consistency in calling 1.000.000 a million and 1.000.000.000 a billion. Moving it backwards, 1.000 should be a zerollion.

    If you want to be consistent, and jump the -llions as a factor of 1.000, start calling 1.000 a “million”, and jump accordingly. Or make 1.000.000 a “bithousand” and 1.000.000.000 a “trithousand”

    On the othe hand, is perfectly consistent to call 10^12 a billion, because it is a million million. TRIllion is a million million million, and so on.

    “And to think they scoff at Americans for not using the metric system”

    Fine, we´ll keep mum about it, and you guys keep losing NASA probes. No problemo.

  9. Arturo Quirantes Sierra Says:

    “I don´t see any consistency in calling 1.000.000 a million and 1.000.000.000 a billion. Moving it backwards, 1.000 should be a zerollion.”

    Sorry, I meant “I do see an inconsistency” That is a meta-inconsistency, hmm?

  10. feldfrei Says:

    Before it gets too boring with ongoing (and repetitive) long/short scale discussions I like to post some thoughts on David’s question for the chance that no two card games have ever started with the same deck:

    http://feldfrei.files.wordpress.com/2011/03/bigblogtheory_cardgame.pdf

  11. Malcolm Lee Says:

    Your blogs are always a delight, but do you all have to be so mean to us Brits in this one. Remember that we came up with the English language in the first place :-)

    This is the age old problem of ‘Two Nations divided by a common language’. I had a quick look into why there ever was any divergence from the original meaning, for which the etymological use of the bi-, tri-, quad-, etc. prefixes appears to me so clear and logical. It seems the first English use of billion in the late 17th century was as a direct import from the French, and meant, like the original French usage, a million million. The French subsequently varied their meaning to a thousand million, and the American mathematician, David E. Smith, records that the US picked up this varied form due in part to French influence after the revolutionary war. http://www.etymonline.com/index.php?term=billion

    In the UK, most who see the word billion in their newspapers would now take it to mean a thousand million, but this is not universal as the UK has never adopted this meaning officially, just in practice. I am old enough to remember the 1974 controversy, which came about when a Conservative (roughly equivalent to Republican) politician Robin Maxwell-Hyslop put a written question about the use of the word billion to the Labour (roughly equivalent to Democrat) Prime Minister, Harold Wilson http://hansard.millbanksystems.com/written_answers/1974/dec/20/billion-definition. Although couched in polite language, it was essentially asking the recently re-elected PM to choose between supporting his country and acquiescing to the Americans. Throughout history, knocking foreigners has been one of the oldest tricks in every country’s political book, and its continuing success – Glenn Beck has made a career out of it – means we are unlikely ever to see the end of this cheap ploy. The PM ducked the anti-Americanism by stating that a thousand million was the ‘international’ meaning for billion. Following on from this, the UK Chancellor of the Exchequer (equivalent to Secretary of the Treasury), Dennis Healey, announced in his 1975 budget statement that any reference in UK government documents to a billion would now mean a thousand million. That was as far as it went on the use of a thousand million over a million million, but there was quite a fuss at the time, with much indignant hot air in the media about replacing good old British meanings with foreign ones, especially US ones! Over 35 years on and this subject can still generate nationalistic passions – http://www.guardian.co.uk/notesandqueries/query/0,5753,-61424,00.html

    Stereotypically, knocking the French is an even better sport here than knocking the US, so if only those 19th century Francophile Americans had called it the French billion we would all know who to blame for this confusion. Freedom billions anyone?

    • David Saltzberg Says:

      Dear Malcolm. Thank you for your detailed and thoughtful reply. I was only teasing the British because we love them. If it weren’t for differences like this we might think that UK is just another part of the U.S., like Canada.

  12. Zig zag zug Says:

    Gah. Probabilities are my one weakness! I have never won a poker game ever. ;-;

    My fav problem is the 2 cups, 1 sip. Don’t google it tho. @___@;;;
    You have one glass of tea and one of water, both same size. They have n molecules each. The tea cup is filled with red balls, the water with blue ones. After you drink 1 random thing out of the tea cup you replace it with a blue one out of the water cup. You keep going until you run out of water, and then run of tea+water.

    Once the water cup is empty, what are the odds you drink a red one? If every ball in the mix can be picked with equal odds, I think it goes:

    P := (n-1)/n*(n-1)/n*(n-1)/n…(n-1)/n

    Which is more clear as:

    P := (1-1/n)(1-1/n)(1-1/n)…(1-1/n)

    And since multiple multiplications are called exponents :

    P := (1-1/n)^n

    And this function can but decrease as you increase the amount of tea+water!

    And if you have enough tea for Sherlock, Spock and Shelley (and maybe a buddy Watson), no one will be surly, so we will surely see: the limit when n is a big number! But who knows what it’ll e^-1?

    • David Saltzberg Says:

      Nice. Of course that final function converges to 1/e (as you hinted). That’s one of my favorite limits. (You need it when deriving the Poisson limit of the binomial distribution which uses large N)

      • Zig zag zug Says:

        There’s something fishy about Poisson distribution! But it’s probably nothing… (hehe!)

        If sums of discrete numbers can describe large amounts of stuff, I just wonder if all the n smaller than 1 or smaller than -1 count for something too! Maybe they all cancel, and so the series and therefore the universe doesn’t diverge. Or maybe we just exclude everything between -1 and 1 (including 1, but not -1!) and so… we have a universe with no center!

        Then I click around on Wikipedia and I get stuff like the Riemann Zeta function and then I feel dumb(er). :D

  13. Card Shuffling: You’re Not Done Yet | Possibly Wrong Says:

    [...] hit” DNA profiling, progressing from there to the birthday problem, and ending with the question of whether it is likely or not that there have ever, in the history of playing cards as we know [...]

  14. Claudio Says:

    Hi,
    I want to create a modern board game about The big bang theory and the Science in general. I’m searching help.

    Someone is interested?
    Do you know how I can get in touch with the admin of the blog?

    Thanks

  15. Kerry Says:

    OK, I’m just finding this blog for the first time (even though I’ve watched and enjoyed BBT from the beginning). I don’t know if anyone is still reading this thread but here’s an answer to David’s “homework” problem on how likely it is for two shuffles of a 52-card deck being the same:

    If there are n possible orderings [8x10^(67) in this case] and m games played [7x10^(18) if 7 billion people each shuffle the deck a billion times], then the probability of NOT having two games the same is

    P(not) = n!/(n-m)!/n^m

    This is exact, and is a generalization of the formula David gave for the birthday problem. Calculating this number is not trivial, but you can approximate it if m and n are large, using Stirling’s approximation for the natural log of a factorial
    ln(n!) ~ n ln(n) – n + ln(2 pi n)/2. Then after some algebra

    ln(P(not)) ~ -(n-m+0.5) ln[1-(m/n)] – m

    Plugging in n=365 and m=23 for the birthday problem, we get David’s answer of about 0.49 for P(not). But for very large n and m (and n much larger than m) it’s still rather tricky because there are some cancellations between the terms.
    Using the approximation ln(1+x) ~ x -x^2/2 +x^3/3, the leading terms are

    ln(P(not)) ~ -m^2/(2n) + m/(2n) -m^3/(6n^2)

    or

    P(not) ~ exp[-m^2/(2n) + m/(2n) -m^3/(6n^2)]

    Once again this gives 0.49 for the birthday problem. For the deck problem, n is much bigger than m and P(not) ~ exp[-m^2/(2n)] is still a good approximation (we can drop the last two terms). Since m^2/n is still much smaller than 1, we can use the approximation exp(1+x) ~ x to get P(not) ~ 1 – m^2/(2n).

    Finally, the probability that two shuffles ARE the same is P(same) = 1 – P(not),
    or just m^2/(2n). For the deck problem this gives about 3×10(-31), still pretty small but much larger than the naive guess of m/n = 9×10^(-50).

  16. S. Brent Morris Says:

    I loved Howard’s card trick! I received my PhD in mathematics from Duke University on the mathematics of card shuffling – “Permutations by Shuffling and Cutting: A Generalization to Q Dimensions,” and went on to patent a computer memory based on principles first discovered by magicians. (Moving cards in a deck is similar to moving data in a memory.) It’s written up in my book published by the Mathematical Association of America, “Magic Tricks, Card Shuffling, and Dynamic Computer Memories.” Martin Gardner wrote the introduction.

Comments are closed.


Follow

Get every new post delivered to your Inbox.

Join 386 other followers

%d bloggers like this: