Italian Solitaire
Combinatorics, Probability; Difficulty: medium
Winning at Italian Solitaire
After a tough geometry/calculus question last week, this week’s Riddler Classic is a counting/probability exercise about a version of Italian Solitaire. The Classic reproduced:
There’s a version of solitaire played in southern Italy with a deck of 40 Neapolitan cards, with four suits numbered from 1 to 10. The deck is shuffled and then cards are turned over one at a time. Flipping over the first card you say “one,” the second card “two” and the third card “three.” You repeat this, saying “one” for the fourth card, “two” for the fifth card and “three” for the sixth card. You continue your way through the deck, until you at last say “one” for the 40th card.
If at any point the number you say matches the value of the card you flip over, you lose.
What is your probability of winning the game?
*spoiler alert* solution and answer follow below
Building intuition with a coin toss (Binomial) approximation
Let’s solve an approximation of the game to build intuition on the likelihood of winning. This game equates to randomly dividing the deck into three piles of 14,13 and 13 cards—labeled one, two and three—and evaluating the probability that each of the twelve cards numbered one, two or three is not in the pile with the same number. As an approximation, assume we assign these cards independently to one of three piles. To win, each of these twelve cards can only be in (some) two of the three piles (and not the third). This occurs with probability \(\frac{2}{3}\) for each card. For all twelve cards, this is equivalent to tossing a (biased) coin with probability of heads \( = \frac{2}{3}\) and getting all 12 heads! You can see immediately that this is going to be a low probability event. The probability in this case is \( \left ( \frac{2}{3} \right )^{12} = 0.77 \% \).
As we will see, this is not too far from the actual answer to the question.
Solution
The entire deck of 40 cards offers 40! equally likely permutations. We need to evaluate how many of these 40! permutations have winning arrangements of the twelve cards—four each numbered 1, 2, and 3.
There are 14 positions called out as ‘1’, and 13 each of the ‘2’ and ‘3’ positions in the deck. In a winning hand, the four 1 cards cannot be in any of 14 positions which the player will callout as ‘1’. The four 2 and four 3 cards cannot be in 13 positions each that the player calls out as ‘2’ or ‘3’ respectively.
For winning hands, let:
– \(i\ (0\leq i\leq 4) \) be the number of 1 cards in the 13 possible ‘2’ position; \(4-i\) ‘1’ cards will consequently be in the 13 possible ‘3’ position.
– \(j\ (0\leq j\leq 4) \) be the number of 2 cards in the 13 possible ‘3’ position; \(4-j\) ‘2’ cards will consequently be in the 14 possible ‘1’ position.
– \(k\ (0\leq k\leq 4) \) be the number of 3 cards in the 14 possible ‘1’ position; \(4-k\) ‘3’ cards will consequently be in the 13 possible ‘2’ position.
Consider just the four 1 cards. There are \({13 \choose i}\) ways to choose \(i\) out 13 ‘2’ positions. Similarly there are \({13 \choose 4-i}\) ways to choose \(4-i\) out of 13 ‘3’ positions. Finally the four 1 cards can be permuted in \(4!\) ways. (Here the \({n \choose r}\) notation refers to the number of ways to choose \(r\) items from \(n\) )
Similarly for the four 2 cards: There are \({13 – (4-i) \choose j}\) ways to choose \(j\) cards out of the remaining \((13 – (4-i))\) ‘3’ positions, since \((4-i)\) slots have been taken by the 1 cards. There are \({14 \choose 4-j}\) ways to choose \(4-j\) out of 14 ‘1’ positions. Finally the four 2 cards can be permuted in \(4!\) ways.
The same logic applies to the four 3 cards. Finally the remaining 28 cards can be permuted in 28! ways.
So, in each situation with given \(i,j,k\), the number of favorable permutations is:
\[
{13 \choose i} {13 \choose 4-i}4!\cdot {13-(4-i) \choose j} {14 \choose 4-j}4!\cdot {14-(4-j) \choose k} {13-i \choose 4-k}4!\cdot 28!
\]
The total number of favorable cases then is just summing this up over all possible values of \(i,j,k\).
\[
\sum_{i=0}^{4} \sum_{j=0}^{4} \sum_{k=0}^{4}{13 \choose i} {13 \choose 4-i}4!\cdot {13-(4-i) \choose j} {14 \choose 4-j}4!\cdot {14-(4-j) \choose k} {13-i \choose 4-k}4!\cdot 28!
\]
That’s a sum of 125 terms that is best calculated writing a short program.
The required probability is then:
\begin{align*}
\displaystyle{P_{win}} &= \frac{\displaystyle{(4!)^3 \cdot 28!\sum_{i=0}^{4} \sum_{j=0}^{4} \sum_{k=0}^{4}{13 \choose i} {13 \choose 4-i}\cdot {13-(4-i) \choose j} {14 \choose 4-j}\cdot {14-(4-j) \choose k} {13-i \choose 4-k}}}{\displaystyle{40!}} \\ \\
&= \frac{6777812804073326003710340862045019176960000000}{815915283247897734345611269596115894272000000000} \\ \\
&\mathbf{{\color{Red} {\approx 0.0083 \ or \ 0.83 \%}}}
\end{align*}
That is less than a 1% chance of winning any single game— pretty low as anticipated—and within 7% of our approximate solution at the top. Be prepared to play quite a while before a win. In fact you’d expect to play \(\frac{1}{0.0083} \approx 120 \) games before winning one!
Modification to increase probability of winning
The game as defined ends the moment we have a number match with position. One way to improve the odds of winning is to allow \(n\ \ (0 \leq n \leq 12)\) matches (fails) before the game is lost. This allows the possibility of up to \(n\) of the 12 cards numbered 1,2, or 3 to be in their respective positions without the game being lost. Note that \(n=0\) is the game as defined in the Riddler question.
If \(in, jn, kn\) represent the number of 1,2 and 3 cards respectively in their positions, it can be shown by extending the logic from the previous section that the number of winning possibilities is:
\[
{\Tiny (4!)^3\cdot 28!\sum_{in=0}^{min(4,n)} \sum_{i=0}^{4-in} \sum_{jn=0}^{min(4,n-in)} \sum_{j=0}^{4 – jn} \sum_{kn=0}^{min(4,n – in-jn)} \sum_{k=0}^{4-kn}{14 \choose in} {13 \choose i}{13 \choose 4-i-in} \cdot {13-i) \choose jn} {13-(4-in-i) \choose 4j}{14-in \choose 4-jn-j} \cdot {13-(4-in-i)-j) \choose kn} {14-in-(4-jn-j) \choose k}{13-i-jn \choose 4-kn-k}}
\]
This can be used to calculate winning probabilities for different values of \(n\ \ (0 \leq n \leq 12)\) with \(n = 0\) being the game defined.
The binomial coin toss approximation is just:
\[
\sum_{i=12-n}^{12}{12 \choose i}\left ( \frac{2}{3} \right )^i\ \left (\frac{1}{3} \right )^{12-i}
\]
The two are plotted below with the actual in blue and the binomial approximation in red.
- The coin toss is a pretty simple yet good approximation
- Allowing matches rapidly increases chances of winning—even 3 matches increases winning chances to ~ 40% !
