

Subject:
Odds of Winning A Simple Solitaire Game
Category: Science > Math Asked by: richardga List Price: $7.50 
Posted:
08 Aug 2002 07:47 PDT
Expires: 07 Sep 2002 07:47 PDT Question ID: 52175 

Subject:
Re: Odds of Winning A Simple Solitaire Game
Answered By: pinkfreudga on 08 Aug 2002 10:44 PDT Rated: 
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 rankderangement 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 RankDerangements" 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 rankderangement problem." Search strategy: "frustration solitaire" ://www.google.com/search?hl=en&ie=UTF8&oe=UTF8&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 
richardga
rated this answer:
Great job pinkfreud. If I ever lose my needle in a haystack I'll know whom to call! 

Subject:
Re: Odds of Winning A Simple Solitaire Game
From: answerguruga on 08 Aug 2002 08:50 PDT 
Richard, Nice game :) I just tried it out a couple times and I got through 51 cards on my second try before losing! answerguruga 
Subject:
Re: Odds of Winning A Simple Solitaire Game
From: gmacga on 08 Aug 2002 09:29 PDT 
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., nonace) 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. 
Subject:
Re: Odds of Winning A Simple Solitaire Game
From: tommoga on 08 Aug 2002 09:36 PDT 
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 cardscards in a suit = 5213 = 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====== (5213) = Cards left  Cards in suit (4^13 * 39!)  52! < Total cards left So given this general equation: s^13 * (n13)!  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 * (3913)!  39! For the third round: 2^13 * (2613)!  26! And for the final round: 1^13 * (1313)!  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 TI82 with me to do these figures elegantly. If there is an error or a question, I will be happy to field it. Tommo 
Subject:
Re: Odds of Winning A Simple Solitaire Game
From: tommoga on 08 Aug 2002 09:43 PDT 
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! 
Subject:
Re: Odds of Winning A Simple Solitaire Game
From: gmacga on 08 Aug 2002 09:44 PDT 
tommoga is computing the probability for a different gamethe probability of matching EVERY card. The original question was whether there NEVER would be a match. 
Subject:
Re: Odds of Winning A Simple Solitaire Game
From: gmacga on 08 Aug 2002 20:13 PDT 
tommoga is computing the probability for a different gamethe probability of matching EVERY card. The original question was whether there NEVER would be a match. 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 