Highest Probability?

Tom Struppeck suggested the following puzzlement. You have a standard 52-card deck of cards. You flip cards until an ace appears. What is the probability that the next card is the ace of spades? (Deuce of clubs?).

Guess the Rule
You were asked to guess the rule for deriving numbers from pairs of numbers. One rule that almost worked was to take the difference of the two numbers, but that failed in one case. The rule that always works is to add the digits of the two numbers, which gives 12 for the missing number.

We had such a great number of correct responses to this puzzle that space only permits us to print a partial list of solvers. This Web version lists all the solvers. Thanks to all who responded.

 Karen AyresRobert BallmerMichael J. BelfattiRachel BerkowitzSuzanne BlackJack BrahmerAmber ButekBoni CaldeiraBarbara ChanShawn ChrismanMatt CrottsRichard DaveyGeorge De GraafMichael ErsevimEduardo EstevaDoreen FagaKyle FalconburySean ForbesDavid GelbergSteve GentleBob Greene David GrimmTerry GuslerGreg HaftJay HallBobby HancockTodd HessBill HossomTim HuffmanLisa HydeJoseph IzzoJulie JoyceRob KahnLawrence KatzJean-Raymond KingsleyRita KwokDamon LayChristopher MosboFritzner MozoulBrian J. MullenJohn Nauss Aaron NewhoffMike RothkaJean-Denis RoyEric SavageJeremy SchallEugene ShevchukSteven SousaChristopher SwanAdam SwartzRajesh ThurairatnamJean-François TremblayDavid UhlandPete VitaSebastian VuDave WesterbergArlene WoodruffSung YimJoshua YoudovinRonald ZaleskiOwen Zhang

Solution to "Card Trick"
As a followup to the recent card trick problem, Tom Struppeck sent the following:

Fitch Cheney could have done a bit better, literally. Recently, a fabulous card trick was described in this column. That trick, attributed to Fitch Cheney, works as follows: an audience member deals five cards from a standard deck. Magician A takes four of the cards, arranges them, and hands them to Magician B. Magician B examines the four cards and then names the fifth card that the audience member still holds. Amazing!

One way of performing the trick was described in the last issue. There are 24 distinct orderings for the four cards given to Magician B and there are five distinct cards that the audience member can be left with, so in principle there are 120 (= 24 x 5) possible messages that can be sent. Since there are only 48 missing cards (Magician B sees four cards out of 52), there is room for an extra "bit" of information (either a "0" or a "1") to be sent, as that would require 96 (= 48 x 2) messages. In particular, the audience member could flip a coin that Magician A sees and Magician B could not only name the remaining card but also tell if the coin was "heads" or "tails."

While there is room in principle, it is not at all obvious that it can actually be done. As it happens, Michael Kleber had previously solved this problem in full generality ("The Best Card Trick," Mathematical Intelligencer, vol. 24, no. 1, Winter 2002. It turns out that the upper bound can always be achieved. One of his proofs is quite elegant, using the Birkoff-von Neumann theorem from linear algebra and the Hall Marriage theorem from combinatorics (and a 225,150,024 x 225,150,024 matrix.) He gives a workable method for the enhanced trick, i.e., one that does not require the performers to consult a table or memorize an inordinate amount of information.