{"id":2269,"date":"2018-04-01T23:00:53","date_gmt":"2018-04-02T04:00:53","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=2269"},"modified":"2018-05-05T00:18:01","modified_gmt":"2018-05-05T05:18:01","slug":"nightmare-solitaire","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/nightmare-solitaire\/","title":{"rendered":"Nightmare Solitaire"},"content":{"rendered":"

This Riddler<\/a> problem is a probability question about an old favorite: Solitaire!<\/p>\n

\nWhile killing some time at your desk one afternoon, you fire up a new game of Solitaire<\/a> (also called Klondike<\/a>, and specifically the version where you deal out three cards from the deck at a time). But your boredom quickly turns to rage because your game is unplayable — you can flip through your deck, but you never have any legal moves! What are the odds?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

I hope you’re in the mood for some counting! First, the basics: the deck contains 52 cards. Once we deal the cards, there are 7 face-up and 21 face-down. That leaves 24 cards in the deck. If we cycle through the deck 3 cards at a time and don’t play any of them, then we will see the same 8 cards over and over again. So whether a particular instance of Solitaire qualifies as “Nightmare” or not is completely characterized by the 7 face-up cards and the 8 deck cards we get to see.<\/p>\n

To compute the probability of dealing a Nightmare game, we’ll count the number of Nightmare games and divide it by the total number of games. When counting, we can restrict our attention to possible choices of the 7+8 cards we see. Of course, the games will play out differently depending on the hidden cards, but these don’t matter for the purpose of counting Nightmare games. Let’s start with the denominator because that’s the easiest thing to calculate:<\/p>\n

Total number of games<\/h3>\n

Since there are 52 total cards, we must choose 7 to be face-up and then choose 8 deck cards. Therefore, the total number of games is:
\n\\[
\nN_\\text{tot} = \\binom{52}{7}\\binom{52-7}{8} = \\frac{52!}{7!\\cdot 8!\\cdot 37!} = 28,837,689,349,669,200
\n\\]As mentioned earlier, we didn’t distinguish between games where the cards we see<\/em> are the same but the hidden cards are different. You might be wondering why the total number of games isn’t just $\\binom{52}{7+8}$. The reason is that the face-up cards and deck cards are not interchangeable. For example, if you have a face-up $3\u2663$ and a $\\color{red}{4\u2665}$ in the deck, there are no legal moves. If instead you have a face-up $\\color{red}{4\u2665}$ and a $3\u2663$ in the deck, you can play the 3 on the 4 when it comes up.<\/p>\n

Counting nightmare games<\/h3>\n

This counting is a bit involved, so we’ll do it in steps. We can partition the cards into two groups:
\n\\begin{align}
\n\\text{Group }1:&\\quad \\left\\{
\n\\begin{array}{rrrrrr}
\n 2\u2660 & 4\u2660 & 6\u2660 & 8\u2660 & 10\u2660 & \\text{Q}\u2660 \\\\
\n \\color{red}{3\u2665} & \\color{red}{5\u2665} & \\color{red}{7\u2665} & \\color{red}{9\u2665} & \\color{red}{\\text{J}\u2665} & \\color{red}{\\text{K}\u2665} \\\\
\n 2\u2663 & 4\u2663 & 6\u2663 & 8\u2663 & 10\u2663 & \\text{Q}\u2663 \\\\
\n \\color{red}{3\u2666} & \\color{red}{5\u2666} & \\color{red}{7\u2666} & \\color{red}{9\u2666} & \\color{red}{\\text{J}\u2666} & \\color{red}{\\text{K}\u2666}
\n\\end{array}\\right\\} \\\\[3mm]
\n\\text{Group }2:&\\quad \\left\\{
\n\\begin{array}{rrrrrr}
\n 3\u2660 & 5\u2660 & 7\u2660 & 9\u2660 & \\text{J}\u2660 & \\text{K}\u2660 \\\\
\n \\color{red}{2\u2665} & \\color{red}{4\u2665} & \\color{red}{6\u2665} & \\color{red}{8\u2665} & \\color{red}{10\u2665} & \\color{red}{\\text{Q}\u2665} \\\\
\n 3\u2663 & 5\u2663 & 7\u2663 & 9\u2663 & \\text{J}\u2663 & \\text{K}\u2663 \\\\
\n \\color{red}{2\u2666} & \\color{red}{4\u2666} & \\color{red}{6\u2666} & \\color{red}{8\u2666} & \\color{red}{10\u2666} & \\color{red}{\\text{Q}\u2666}
\n\\end{array}\\right\\}
\n\\end{align}These groups were chosen in a particular way: cards from each group can only be played on other cards from the same group. For example, $\\color{red}{6\u2665}$, which is in Group 2, can only be played on $7\u2660$ or $7\u2663$, which are also in Group 2. Cards from the two groups never interact with one another. The four aces have been left out because any visible ace (either face-up or in the deck) is always playable. Let’s take it one step at a time.<\/p>\n

A 12-card deck, face-up only.<\/b> Let’s start with a simpler problem. What if the deck only consisted of the top half of Group 1, namely:
\n\\[
\n\\text{Mini-deck}:\\quad \\left\\{
\n\\begin{array}{rrrrrr}
\n 2\u2660 & 4\u2660 & 6\u2660 & 8\u2660 & 10\u2660 & \\text{Q}\u2660 \\\\
\n \\color{red}{3\u2665} & \\color{red}{5\u2665} & \\color{red}{7\u2665} & \\color{red}{9\u2665} & \\color{red}{\\text{J}\u2665} & \\color{red}{\\text{K}\u2665}
\n\\end{array}\\right\\}
\n\\]In this $n$-card deck ($n=12$), how many ways can we choose $k$ face-up cards so that there are no moves available? This is a classic “stars and bars<\/a>” problem. This is equivalent to counting the subsets of size $k$ such that no two adjacent cards are picked. Since we are choosing $k$ cards, we must exclude $k-1$ buffer cards in between the chosen cards. Therefore, there are $f(n,k) = \\binom{n-k+1}{k}$ possible choices.<\/p>\n

12-card deck, full version.<\/b> Using the same mini-deck as above, let’s ask a harder question: How many ways can we choose $k$ face-up cards and<\/em> $p$ deck cards so that there are no moves available? This is a bit trickier. A card in the deck is playable precisely when it is one less<\/em> than one of the face-up cards. However, the number of cards that are one less depends on whether we have a face-up $2$ or not (since our deck has no aces). So let’s distinguish two cases:<\/p>\n

    \n
  1. We have a face-up $2$, which means we can’t use a face-up $3$ either. There are therefore $f(n-2,k-1) = \\binom{n-k}{k-1}$ possible choices. There are also $k-1$ cards that are one less than the face-up cards. We must therefore choose our $p$ deck cards from the remaining $n-k-(k-1)$ cards.\n
  2. We do not have a face-up $2$. There are $f(n-1,k) = \\binom{n-k}{k}$ possible choices. There are also $k$ cards that are one less than the face-up cards we chose. We must therefore choose our $p$ deck cards from the remaining $n-2k$ cards.\n<\/ol>\n

    So in total, there are $\\binom{n-k}{k-1}\\binom{n-2k+1}{p}+\\binom{n-k}{k}\\binom{n-2k}{p}$ ways of choosing our $k$ face-up cards and $p$ deck cards in the mini-deck case.<\/p>\n

    Group 1 deck, full version.<\/b> Let’s expand our deck to include all the cards from Group 1. Again, we want to pick $k$ face-up cards and $p$ deck cards such that no moves are possible. Let $m$ be how many different card numbers we use (e.g. if we only use 2’s and 6’s, then $m=2$). This is similar to the mini-deck case, except now we’re picking how many different card numbers there will be, and then<\/em> picking the cards themselves. For example, if we have a face-up $2$, then there are $f(n-2,m-1) = \\binom{n-m}{m-1}$ possible choices of for the card numbers. To pick the cards themselves, we must choose $k$ cards from $m$ groups of $2$, with at least one card picked per group. There are $\\binom{m}{k-m}$ ways of picking the cards if the cards in each group are indistinguishable, but since they are not, we must also multiply by $2$ for each group that only had one card picked, i.e. $m-(k-m)$. Now for the $p$ deck cards… There were $m$ groups picked (including the groups of two), which means $m-1$ groups are forbidden. They have $2$ cards each, so that’s $2m-2$ cards we can’t use. We started with $2n$ cards and we picked $k$ already. This means we must choose the $p$ deck cards from the remaining $2n-(2m-2)-k$. Putting everything together and including the case with no face-up $2$s, we have:
    \n\\begin{multline}
    \ng(n,k,p) = \\sum_{m=0}^k \\left[ \\binom{n-m}{m-1}\\binom{2n-2m-k+2}{p}\\right.\\\\
    \n+\\left.\\binom{n-m}{m}\\binom{2n-2m-k}{p} \\right] \\binom{m}{k-m} 2^{2m-k}
    \n\\end{multline}The reason we’re summing over $m$ is because we must account for every possible number of card distinct card number, which naturally can’t exceed $k$. Here, binomial coefficients are being interpreted in the combinatorial sense, so we’re using the convention that $\\binom{a}{b} = 0$ if $a\\lt 0$, $b\\lt 0$, or $b\\gt a$.<\/p>\n

    The full deck.<\/b> For the full deck, it turns out most of the work has already been done! When combining the cards from Group 1 and Group 2, they don’t ever interact with one another. So ultimately, we just need to decide how many cards from each of the groups we should include in the face-up and deck cards so there are 7 and 8 in total, respectively. The net result is:
    \n\\begin{align}
    \nN_\\text{nightmare} &= \\sum_{i=0}^7 \\sum_{j=0}^8 g(12,i,j)\\cdot g(12,7-i,8-j) \\\\
    \n&= 72,099,595,172,416
    \n\\end{align}<\/p>\n

    Taking the ratio $\\frac{N_\\text{nightmare}}{N_\\text{total}}$ and simplifying we obtain our final answer:<\/p>\n

    $\\displaystyle
    \n\\mathbb{P}(\\text{nightmare game}) = \\frac{643746385468}{257479369193475} \\approx 0.25\\%
    \n$<\/span><\/p>\n

    To get an idea for the size of this number, here is a plot that shows the probability of having had at least one nightmare game given that you’ve played $N$ games in total. In other words, if $p$ is the probability of having a nightmare game, this is a plot of $1-(1-p)^N$.<\/p>\n

    \"\"<\/a><\/p>\n

    You would have to play roughly 277 games of solitaire so that the probability of having encountered at least one nightmare game is 50%. <\/p>\n

    Bonus: alternative rules<\/h3>\n

    If instead we play the variant of Solitaire where you flip only one card at a time, then we can compute the probability of a nightmare game using the same tools as above. The only difference is that we have $24$ deck cards rather than $8$. The probability of a nightmare game using these rules is:
    \n\\begin{align}
    \n&\\hspace{-1cm}\\mathbb{P}(\\text{nightmare game, 1-card variant}) \\\\
    \n&= \\frac{ \\sum_{i=0}^7 \\sum_{j=0}^{24} g(12,i,j)\\cdot g(12,7-i,24-j) }{ \\binom{52}{7}\\binom{52-7}{24} } \\\\
    \n&= 1.77016\\times 10^{-7}
    \n\\end{align}The probability is much smaller for this 1-card variant because we see so much more of the deck; a lot more has to “go wrong” to have a nightmare scenario. Here is what the graph looks like for the 1-card variant; it looks similar to the 3-card graph, but shifted far to the right ($N$ is much larger).<\/p>\n

    \"\"<\/a><\/p>\n

    To put this in context, when you go from the 3-card variant to the 1-card variant, nightmare games are $14,\\!100$ times more unlikely. <\/p>\n

    Other solutions<\/h3>\n

    As you might expect, I’m not the first to have computed the probability of a Klondike game being unplayable. The Wikipedia entry<\/a> confirms the probability is 0.25%, but the links provided use Monte Carlo simulations<\/a> rather than direct counting. The only other exact solutions I could find were an optimized brute-force approach by Donkersteeg<\/a> and a dynamic programming (recursive) approach by de Ruiter<\/a>. Both recover the exact same solution as above.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

    This Riddler problem is a probability question about an old favorite: Solitaire! While killing some time at your desk one afternoon, you fire up a new game of Solitaire (also called Klondike, and specifically the version where you deal out three cards from the deck at a time). But your boredom quickly turns to rage … Continue reading “Nightmare Solitaire”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2286,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[6,8,2],"class_list":["post-2269","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-counting","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2269","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=2269"}],"version-history":[{"count":23,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2269\/revisions"}],"predecessor-version":[{"id":2300,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2269\/revisions\/2300"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2286"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2269"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2269"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2269"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}