Here is what you might call the world's simplest solitaire game:

Shuffle a standard 52-card deck and deal it out face up in a single
pile.  As you deal, count out 1-2-3-4-5-6-7-8-9-10-J-Q-K four times to
coincide with each card in sequence.  At any time that the card you
'name' matches the card you deal you can stop--you've lost.  If you
get through all 52 cards without a match, you've won.

If you try this game, you'll find that you lose almost every time.  On
the other hand, it's easy to 'stack' a winning deck.

My question (which I've puzzled over for years) is what are the odds
of winning this game?  No brute force, please--it would be interesting
to know how many winning hands a computer can deal in a billion tries,
but I'd appreciate an analytical solution.

---

Clarification of Question by richard-ga on 08 Aug 2002 07:54 PDT

The suit of the card is irrelevant--only the number of the card matters.

Greetings, Richard.

The name of this form of solitaire is "Frustration Solitaire." It was
the very first solitaire game I ever learned (however, I abandoned it
in favor of "Klondike" shortly thereafter.)

Dartmouth College has reprinted online this interesting article by
Marilyn vos Savant (who is billed as "The Smartest Person on Earth.")
The article first appeared in Parade Magazine's "Ask Marilyn" column
in 1994.

"Charles Price is baffled by the following problem:  Take 
an ordinary deck of 52 cards and shuffle it. Then turn 
the cards over one at a time, counting as you go: ace, 
two, three, and so on, until you reach king; then start 
over again.  The object is to turn over all 52 cards 
without having your spoken number match the card in rank 
that you turn over.

Charles mentions that he has tried it hundreds of time 
and only once turned over all the cards with no match.  
He expected it to happen more often. Obviously, he 
wanted to know the chance of getting through the deck 
without a rank match, but he has to settle for Marilyn 
telling him only that the expected number of matches is 
4 so he should not expect to succeed very often. 

The origin of matching problems like this and the 
related "hat check problem" can be found in a book 
Montmort written in 1708 to help explain some of the 
common games of the time that involved probability-- in 
particular, the game of Treise played as follows:  

One player is chosen as the banker and the others are 
players.  Each player  puts up a stake. The banker 
shuffles the cards and  starts dealing calling out the 
cards in order ace, two, three, ... ,king. The game 
continues until there is a rank coincidence or the 
banker has dealt thirteen cards without such a 
coincidence.  If there is no match, the banker pays the 
players an amount equal to their stakes and a new dealer 
is chosen. If there is a match he wins from the players 
an amount equal to their stake and starts a new round 
counting again ace, two, three, etc.  If runs out of 
cards he  reshuffles and continues the count where he 
left off.

Montmort remarks that the dealer has a very favorable 
game and could easily get several matches before losing 
the deal. He despairs of finding the actual advantage
but solves some related problems.  He first simplified 
the game by assuming that the deck of cards had only 13 
cards of one suit.  He then found that the probability 
of getting through the 13 cards without a match was 
about 1/e = .368 providing the first solution to what is 
now called the "hat check" problem. Later, with the help 
of John Bernoulli he showed that in drawing 13 cards 
from a 52 card deck the chance of not getting a rank 
match was .357 making it clear that the dealer has a 
considerable advantage. 

In the problem that Charles suggested you are to go 
through the entire deck of 52 cards and this makes the 
problem harder because you can have different match 
patterns.  Your matches might be with distinct ranks or 
with the same ranks or both.
 
We called Charles to see where he found the problem and 
he said that it was a solitaire game that a friend had 
suggested. Evidently, if you get your letter in 
Marilyn's column you become an instant celebrity and get 
lots of phone calls.  One of his more interesting calls 
was from a Steven Landfedler. We called Steven and he 
told us a story about a lifelong obsession with this 
problem.

He learned this game of solitaire from his grandmother 
Enrestine Landfelder who was a gypsy from Eastern Europe 
who played a lot of cards.  She called it "frustration 
solitaire" .  Steven was 15 at the time (1956) and tried 
to find the chance of winning but it was too hard for 
him.

He became obsessed with finding the solution. As 
he grew older he was better able to read math 
books but this was certainly not his specialty.  
He found references that solved the problem but 
said things like "carrying out "difficult but 
routine calculations" or, worse yet, mentioned 
ideas that were a complete mystery to him such as 
"using Rook Polynomials". (For a solution using 
the connection to Rook Problems see Riordan's  
"Introduction to  Combinatorial Analysis.")

However, Steven persevered and, using what he had 
gleamed from his reading, was able to work out the 
solution to his satisfaction.  He remarked that he 
still wanted to find an explanation that he could 
give to his daughter who is a math teacher.  We 
will try to write up such an explanation.  If we 
succeed we will put on the Chance Data Base in 
Teaching Aids. (Now who's obsessed with this 
problem!)"

Marilyn Vos Savant, "Ask Marilyn: Hat Check Problem"
http://www.dartmouth.edu/~chance/chance_news/recent_news/chance_news_3.12.html

Peter G. Doyle, Charles Grinstead, and J. Laurie Snell, of Dartmouth,
have written a paper that greatly expands upon the above article.
Below is the abstract from that paper, with a link to the full text.

"In this expository article, we discuss the rank-derangement problem,
which asks for the number of permutations of a deck of cards such that
each card is replaced by a card of a different rank. This
combinatorial problem arises in computing the probability of winning
the game of `frustration solitaire', which was the subject of a recent
column by Marilyn vos Savant. The solution by means of the method of
inclusion and exclusion is a prime example of the use of this simple
yet powerful method."

Peter G. Doyle et al.: "Frustration Solitaire and Rank-Derangements"
http://hilbert.dartmouth.edu/~doyle/docs/rank/rank/rank.html

I believe you will find the analytical solution that you seek within
the elegant paper by Doyle, Grinstead, and Snell. See particularly the
section entitled "Solution of the rank-derangement problem."

Search strategy: "frustration solitaire"
://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=%22frustration+solitaire

Thank you for asking a most intriguing question. Before rating my
answer, please ask for clarification if it is needed.

Cordially,
pinkfreud

Great job pinkfreud.
If I ever lose my needle in a haystack I'll know whom to call!

Richard,

Nice game :)

I just tried it out a couple times and I got through 51 cards on my
second try before losing!

answerguru-ga

What makes most solitaire games interesting is that they do not have
analytical solutions.  I think an analytical solution to this one
would be a mess.  In some sense it is a more complicated version of
the birthday problem which yo might want to search for on the web.

What is the probability of surviving the first card?  That is easy. 
There are 48 safe (i.e., non-ace) possibilities and 52 total
possibilities so the probability is 48/52 = 12/13 = 0.923077.

What is the probability of surviving the second card?  Not so easy
because it depends on whether the first card was a deuce or not.  If
it were a deuce, then one of the dangerous cards for the second draw
has been used up so our probability of surviving the 2nd draw is
48/51, but if the first card were not a deuce, then things are a
little riskier at 47/51.  So, the probability of surviving the 2nd
draw (given that we survived the first one) equals
(1/12)(48/51) + (11/12)(47/51) = .923203.   Notice that this is every
so slightly higher than our chances on the first draw.   I think it
will be the case that chances of surviving generally increase on each
draw because there has been more opportunity for dangerous cards to
have been used up.

In any case, the probability of surviving BOTH the first and second
draws equals .923077 * .923203 = .852187

It will get messy to go further because for the 3rd draw we have to
consider the probability that none, one, or two 3's have been used up
on the first two draws.  Dealing with these conditional dependencies
will get very ugly.

However, ff draws do get relatively safer as I've suggested below,
then we can get a lower bond for the survival probabilty by using the
.923077 probability for all 52 draws.  .923077^52 = .0155729.   So at
a minimum, one should win your simple solitaire game about once or
twice for every 100 games.

Hello there,

The answer I give comes only from doing similiar problems over the
past year in discrete math courses, of which I have a passive
understanding at this point. I am interested in the
validation/discredit of my solution so I will post it.


Since you want to deal out all of the cards in a fashion where
numbered order matters but the suit does not, we should be able to
solve this with a series of smaller problems. There are 52 cards in a
deck, 4 suits, and 13 cards to each suit.

Beginning the game, you have a 4/52 chance of drawing that first ace
(i am calling aces low, as in a usual solitare game). This is so
because, at first, there are four aces for you to draw out of a 52
card deck.

Now we want a 2, there is a 4/51 chance of drawing this next 2 - again
there are four 2s in the deck, but now, since we can assume we already
drew an ace (because we are only counting valid patterns, if another
card was drawn, we stop at a loss) there are now 51 cards to chose
from.

The pattern that follows is listed below:

Card Drawn:      Odds:       
    A             4/52
    2             4/51
    3             4/50 
    ...
    ...
    J             4/42
    Q             4/41
    K             4/40             

Note that the odds for the king are 4/40 and not 4/39 (total
cards-cards in a suit = 52-13 = 39) because the odds are determined
before the king is drawn, therefore only cards up to the queen count
as drawn.

From the above pattern, we can derive the equation following equation
for determining the odds of successfully drawing this sequence once:

Let the carrot (^) denote power, so that 4^13 is 4 to the 13th power.

(4*4*4*4*4*4*4*4*4*4*4*4*4) / (52*51*50*49*48*47*46*45*44*43*42*41*40)

which we can simplify as:

4^13 / [(52!) / (39!)]

Bringing the 39 factorial into the numerator we get:

(4^13 * 39!) / 52!

And as an actual number:

1.69*10^-14 or .00000000000169% chance just for just one drawing

Now that we've seen how to do the process for one drawing, lets speed
things up and look at a few numbers in the equation:

(number of cards left in the suit) 4 ^ 13 (number of cards in the
suit)
                         |
                         V       V====== (52-13) = Cards left - Cards
in suit
                        (4^13 * 39!) 
                        -------------
                             52!  <------  Total cards left


So given this general equation:
         
                s^13 * (n-13)!
              ------------------
                      n!
where s is the number of cards left in the suit and n is the number of
cards in
the deck (when starting the draw, before the ace is drawn).

So for the second round of solitaire, the equation reads:

             3^13 * (39-13)!
           -------------------
                   39!

For the third round:

             2^13 * (26-13)!
           --------------------
                    26!

And for the final round:

             1^13 * (13-13)!
           --------------------
                   13!

Notice that for the final round the result is simply 1 / 13! (note
that 0! is 1, not 0) which is the odds of drawing 13 cards in order
out of an ordered deck - which is basically what the game has come to
for the final drawing.


Putting all of these results together gives the odds of winning this
game:

First round       Second round           Third round     Fourth round

(4^13 * 39!)        3^13 * 26!            2^13 * 13!         1
------------  *  ----------------  *  ----------------- *  -----
    52!                39!                   26!            13!

You (or someone) may have to check my math here, as I am using windows
calculator to do the arithmetic (yuck), but the answer that I have
yielded is:


1.69 * 10^-14 *   3.15 * 10^-14    *  1.26 * 10^-13     *  1.60 *
10^-10

Multiplying out, I got

1.07 * 10^-50 
or 
.00000000000000000000000000000000000000000000000107% Chance
or
.0000000000000000000000000000000000000000000000000107 as a probability
or 
1 time out of 90,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

Which is certainly a miniscule chance of success! As a basis for
comparison, the chances of getting a royal flush in a five card stud
poker game is 0.00000154

I have double checked my arithmetic but I do not have my trusty TI-82
with me to do these figures elegantly. If there is an error or a
question, I will be happy to field it.

-Tommo

Hey there, rereading your question, i solved the reverse problem! I
read any card that 'matches' you stop as any card thay does not match
you stop - o well!

tommo-ga is computing the probability for a different game--the
probability of matching EVERY card.  The original question was whether
there NEVER would be a match.

tommo-ga is computing the probability for a different game--the
probability of matching EVERY card.  The original question was whether
there NEVER would be a match.