Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1994 AIME Problems/Problem 9"

(solution by phelphedo)
(solution 3)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
A solitarire 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.  The probability that the bag will be emptied is <math>p/q,\,</math> where <math>p\,</math> and <math>q\,</math> are relatively prime positive integers.  Find <math>p+q.\,</math>
+
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.  The probability that the bag will be emptied is <math>p/q,\,</math> where <math>p\,</math> and <math>q\,</math> are relatively prime positive integers.  Find <math>p+q.\,</math>
  
 
== Solution ==
 
== Solution ==
Line 10: Line 10:
  
 
Therefore, we obtain the [[recursion]] <math>P_k = \frac {3}{2k - 1}P_{k - 1}</math>. Iterating this for <math>k = 6,5,4,3,2</math> (obviously <math>P_1 = 1</math>), we get <math>\frac {3^5}{11*9*7*5*3} = \frac {9}{385}</math>, and <math>p+q=\boxed{394}</math>.
 
Therefore, we obtain the [[recursion]] <math>P_k = \frac {3}{2k - 1}P_{k - 1}</math>. Iterating this for <math>k = 6,5,4,3,2</math> (obviously <math>P_1 = 1</math>), we get <math>\frac {3^5}{11*9*7*5*3} = \frac {9}{385}</math>, and <math>p+q=\boxed{394}</math>.
 +
 +
==Solution 2==
 +
Call the case that we begin with [ABCDEF]. It doesn't matter what letter we choose at first, so WLOG assume we choose A. Now there is BCDEFABCDEF remaining in the bag. We have two cases to consider here.
 +
 +
1. We pick the other A. There's a <math>\frac{1}{11}</math> chance for this to happen. We remain with the case [BCDEF] if this is the case.
 +
 +
2. We pick any other letter that is not an A. There's a <math>\frac{10}{11}</math> chance for this to happen. WLOG, assume we pick the letter B. Now in order for us to continue the game, we must choose either the other A or B. There's a <math>\frac{2}{10}</math> chance for this to happen. WLOG, assume we choose A. Now we have BCDEFCDEF left.
 +
 +
Notice however that in the first case, the probability of emptying the bag with [BCDEF] is the same thing as with BCDEFCDEF, as the only difference is you've removed one of the letters (and it doesn't matter which you chose).
 +
 +
Hence for this case, there is a <math>\frac{1}{11} + \frac{10}{11}*\frac{2}{10} = \frac{3}{11}</math> * [BCDEF] chance to empty the bag.
 +
 +
Continuing this process, we get that:
 +
 +
[BCDEF] = <math>\frac{3}{9}</math> * [CDEF]
 +
 +
[CDEF] = <math>\frac{3}{7}</math> * [DEF]
 +
 +
[DEF] = <math>\frac{3}{5}</math> * [EF]
 +
 +
[EF] = 1 (clearly, since if we are only left with EFEF then we are going to empty the bag).
 +
 +
And hence [ABCDEF] = <math>1*\frac{3}{5}*\frac{3}{7}*\frac{3}{9}*\frac{3}{11} = \frac{9}{385}</math> so our answer is <math>9+385=\boxed{394}</math>
 +
 +
==Solution 3==
 +
Let <math>a_{m,n}</math> represent the situation in which <math>n</math> tiles are in your hand and <math>m</math> pairs have been removed; i.e., there are <math>2m</math> tiles remaining in play. We know that <math>a_{m,0}=a_{m,1}</math> to begin with, so we find some other recursions:
 +
 +
When the player has <math>1</math> tile in their hand with <math>m</math> pairs remaining, there is a <math>\frac{1}{2m-1}</math> chance that the player finds the one matching tile and the game state changes to <math>a_{m-1,0}</math>. There is a <math>\frac{2m-2}{2m-1}</math> chance that the player does not find the matching tile and the game state changes to <math>a_{m,2}</math>. As a result, <math>a_{m,1}=\frac{1}{2m-1}a_{m-1,0}+\frac{2m-2}{2m-1}a_{m,2}</math>.
 +
 +
When the player has <math>2</math> tiles in their hand with <math>m</math> pairs remaining, there is a <math>\frac{1}{m-1}</math> chance that the player finds a matching tile and the game moves on to game state <math>a_{m-1,1}</math>. As a result, <math>a_{m,2}=\frac{1}{m-1}a_{m-1,1}</math>.
 +
 +
We also know that <math>a_0=a_1=a_2=1</math> (i.e., you are guaranteed to win with two tiles remaining), so we are able to find an end to the recursion.
 +
 +
Now we are left with four rules:
 +
 +
1) <math>a_{m,0}=a_{m,1}</math>
 +
 +
2) <math>a_{m,1}=\frac{1}{2m-1}a_{m-1,0}+\frac{2m-2}{2m-1}a_{m,2}</math>
 +
 +
3) <math>a_{m,2}=\frac{1}{m-1}a_{m-1,1}</math>
 +
 +
4) <math>a_0=a_1=a_2=1</math>
 +
 +
We then calculate the terms of the multi-variable recursion and arrive at <math>a_{6,0}=\frac{9}{385}</math>, so the answer is <math>385+9=\boxed{394}</math>.
 +
 +
~eevee9406
  
 
== See also ==
 
== See also ==
Line 15: Line 61:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:49, 20 July 2024

Problem

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. The probability that the bag will be emptied is $p/q,\,$ where $p\,$ and $q\,$ are relatively prime positive integers. Find $p+q.\,$

Solution

Let $P_k$ be the probability of emptying the bag when it has $k$ pairs in it. Let's consider the possible draws for the first three cards:

  • Case 1. We draw a pair on the first two cards. The second card is the same as the first with probability $\frac {1}{2k - 1}$, then we have $k - 1$ pairs left. So this contributes probability $\frac {P_{k - 1}}{2k - 1}$.
  • Case 2. We draw a pair on the first and third cards. The second card is different from the first with probability $\frac {2k - 2}{2k - 1}$ and the third is the same as the first with probability $\frac {1}{2k - 2}$. We are left with $k - 1$ pairs but one card already drawn. However, having drawn one card doesn't affect the game, so this also contributes probability $\frac {P_{k - 1}}{2k - 1}$.
  • Case 3. We draw a pair on the second and third cards. This is pretty much the same as case 2, so we get $\frac {P_{k - 1}}{2k - 1}$.

Therefore, we obtain the recursion $P_k = \frac {3}{2k - 1}P_{k - 1}$. Iterating this for $k = 6,5,4,3,2$ (obviously $P_1 = 1$), we get $\frac {3^5}{11*9*7*5*3} = \frac {9}{385}$, and $p+q=\boxed{394}$.

Solution 2

Call the case that we begin with [ABCDEF]. It doesn't matter what letter we choose at first, so WLOG assume we choose A. Now there is BCDEFABCDEF remaining in the bag. We have two cases to consider here.

1. We pick the other A. There's a $\frac{1}{11}$ chance for this to happen. We remain with the case [BCDEF] if this is the case.

2. We pick any other letter that is not an A. There's a $\frac{10}{11}$ chance for this to happen. WLOG, assume we pick the letter B. Now in order for us to continue the game, we must choose either the other A or B. There's a $\frac{2}{10}$ chance for this to happen. WLOG, assume we choose A. Now we have BCDEFCDEF left.

Notice however that in the first case, the probability of emptying the bag with [BCDEF] is the same thing as with BCDEFCDEF, as the only difference is you've removed one of the letters (and it doesn't matter which you chose).

Hence for this case, there is a $\frac{1}{11} + \frac{10}{11}*\frac{2}{10} = \frac{3}{11}$ * [BCDEF] chance to empty the bag.

Continuing this process, we get that:

[BCDEF] = $\frac{3}{9}$ * [CDEF]

[CDEF] = $\frac{3}{7}$ * [DEF]

[DEF] = $\frac{3}{5}$ * [EF]

[EF] = 1 (clearly, since if we are only left with EFEF then we are going to empty the bag).

And hence [ABCDEF] = $1*\frac{3}{5}*\frac{3}{7}*\frac{3}{9}*\frac{3}{11} = \frac{9}{385}$ so our answer is $9+385=\boxed{394}$

Solution 3

Let $a_{m,n}$ represent the situation in which $n$ tiles are in your hand and $m$ pairs have been removed; i.e., there are $2m$ tiles remaining in play. We know that $a_{m,0}=a_{m,1}$ to begin with, so we find some other recursions:

When the player has $1$ tile in their hand with $m$ pairs remaining, there is a $\frac{1}{2m-1}$ chance that the player finds the one matching tile and the game state changes to $a_{m-1,0}$. There is a $\frac{2m-2}{2m-1}$ chance that the player does not find the matching tile and the game state changes to $a_{m,2}$. As a result, $a_{m,1}=\frac{1}{2m-1}a_{m-1,0}+\frac{2m-2}{2m-1}a_{m,2}$.

When the player has $2$ tiles in their hand with $m$ pairs remaining, there is a $\frac{1}{m-1}$ chance that the player finds a matching tile and the game moves on to game state $a_{m-1,1}$. As a result, $a_{m,2}=\frac{1}{m-1}a_{m-1,1}$.

We also know that $a_0=a_1=a_2=1$ (i.e., you are guaranteed to win with two tiles remaining), so we are able to find an end to the recursion.

Now we are left with four rules:

1) $a_{m,0}=a_{m,1}$

2) $a_{m,1}=\frac{1}{2m-1}a_{m-1,0}+\frac{2m-2}{2m-1}a_{m,2}$

3) $a_{m,2}=\frac{1}{m-1}a_{m-1,1}$

4) $a_0=a_1=a_2=1$

We then calculate the terms of the multi-variable recursion and arrive at $a_{6,0}=\frac{9}{385}$, so the answer is $385+9=\boxed{394}$.

~eevee9406

See also

1994 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 8 		Followed by
Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_AIME_Problems/Problem_9&oldid=223207"