From the AIME competion: Probability of winning solitaire-type game

combinatoricscontest-mathprobabilityprobability distributions

A question from the AIME competition, see here: https://artofproblemsolving.com/wiki/index.php/1994_AIME_Problems/Problem_9

A solitaire game is played as follows. Six distinct pairs of matched tiles are placed in a bag. The player randomly draws tiles one at a time from the bag and retains them, except that matching tiles are put aside as soon as they appear in the player's hand. The game ends if the player ever holds three tiles, no two of which match; otherwise the drawing continues until the bag is empty. Find the probability that the player wins the game (by emptying the bag).

Here's what I did. The probability the player wins the game is$$1 – \text{probability of player losing the game},$$so let's compute that instead. Let's now count the cases of losing and add them up:

  • Probability of getting a sequence xyz from the start: $6(5)(4){{2^3}\over{12(11)(10)}} = {8\over{11}}$
  • Probability of getting either sequence aaxyz or xaayz from the start: $2(6)(5)(4)(3){{2^4}\over{12(11)(10)(9)(8)}} = {4\over{33}}$
  • Probability of getting either sequence aabbxyz, aaxbbyz, or xaabbyz from the start: $3(6)(5)(4)(3)(2){{2^5}\over{12(11)(10)(9)(8)(7)(6)}} = {4\over{231}}$
  • Probability of either getting either sequence aabbccxyz, aabbxccyz, aaxbbccyz, or xaabbccyz from the start: $4(6)(5)(4)(3)(2)(1){{2^6}\over{12(11)(10)(9)(8)(7)(6)(5)(4)}} = {8\over{3465}}$

Therefore, I calculate the probability of the player winning the game to be$$1 – \left({8\over{11}} + {4\over{33}} + {4\over{231}} + {8\over{3465}}\right) = {{457}\over{3465}}$$However, the answer in the link above is ${9\over{385}}$. So then where did I go wrong?

Edit: The current answers below just reproduce the answers given in the link. I am wondering how to modify my incorrect solution into a correct solution.

Best Answer

Ok, so the probability of player winning the game is $1 - \text{probability of player losing the game}$. Let $x$, $y$ and $z$ represent the tiles retained, and $a$, $b$ and $c$ represent the tiles put aside. Let $n$ be the number of pairs of tiles put aside before the lost.

  • For $n=0$, there is $1$ unique possible sequence xyz.
  • For $n=1$, there are $3$ possible sequences, aaxyz, axayz and xaayz.
  • For $n=2$, there are $9$ possible sequences, aabbxyz, aabxbyz, aaxbbyz, ababxyz, abaxbyz, axabbyz, baabxyz, baaxbyz and xaabbyz.
  • For $n=3$, there are $27$ possible sequences, aabbccxyz, aabbcxcyz, aabbxccyz, aabcbcxyz, aabcbxcyz, aabxbccyz, aacbbcxyz, aacbbxcyz, aaxbbccyz, ababccxyz, ababcxcyz, ababxccyz, abacbcxyz, abacbxcyz, abaxbccyz, acabbcxyz, acabbxcyz, axabbccyz, baabccxyz, baabcxcyz, baabxccyz, baacbcxyz, baacbxcyz, baaxbccyz, caabbcxyz, caabbxcyz and xaabbccyz.
  • For $n=m$, there are $3^m$ possible sequences.

Therefore,

  • For $n=0$, the probability of player losing the game is $${2^3 \cdot {6!\over 3!}\over {12!\over 9!}}= {8 \over 11}$$
  • For $n=1$, the probability of player losing the game is $${3 \cdot 2^4 \cdot {6!\over 2!}\over {12!\over 7!}}={2 \over 11}$$
  • For $n=2$, the probability of player losing the game is $${3^2 \cdot 2^5 \cdot {6!\over 1!}\over {12!\over 5!}}={4 \over 77}$$
  • For $n=3$, the probability of player losing the game is $${3^3 \cdot 2^6 \cdot {6!\over 0!}\over {12!\over 3!}}={6 \over 385}$$

The general formula of the probability $P$ of player losign the game for $k$ pair of tiles originally placed on the bag and $m \leq k-3$ pairs of tiles put aside before the lost would be $$P={3^m \cdot 2^{(3+m)} \cdot {(k)!\over (k-3-m)!}\over {(2k)!\over (2k-3-2m)!}}$$

Therefore, the probability of winning the game is $$1-{8 \over 11}-{2 \over 11}-{4 \over 77}-{6 \over 385}={9 \over 385}$$

I guess you should also be able to calculate it more directly, but there it is.

Related Question