Difference between revisions of "2015 AIME I Problems/Problem 5"

Latest revision as of 22:33, 23 January 2024

Problem

In a drawer Sandy has $5$ pairs of socks, each pair a different color. On Monday Sandy selects two individual socks at random from the $10$ socks in the drawer. On Tuesday Sandy selects $2$ of the remaining $8$ socks at random and on Wednesday two of the remaining $6$ socks at random. The probability that Wednesday is the first day Sandy selects matching socks is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers, Find $m+n$ .

Solution 1

Let the fifth sock be arbitrary; the probability that the sixth sock matches in color is $\dfrac{1}{9}$ .

Assuming this, then let the first sock be arbitrary; the probability that the second sock does not match is $\dfrac{6}{7}.$

The only "hard" part is the third and fourth sock. But that is simple casework. If the third sock's color matches the color of one of the first two socks (which occurs with probability $\dfrac{2}{6} = \dfrac{1}{3}$ ), then the fourth sock can be arbitrary. Otherwise (with probability $\dfrac{2}{3}$ ), the fourth sock can be chosen with probability $\dfrac{4}{5}$ (5 socks left, 1 sock that can possibly match the third sock's color). The desired probability is thus $\frac{1}{9} \cdot \frac{6}{7} \cdot \left(\dfrac{1}{3} + \dfrac{2}{3} \cdot \dfrac{4}{5}\right) = \frac{26}{315}.$ The sum is therefore $26+315=\boxed{341}.$

Solution 2

The key is to count backwards. First, choose the pair which you pick on Wednesday in $5$ ways. Then there are four pairs of socks for you to pick a pair of on Tuesday, and you don't want to pick a pair. Since there are $4$ pairs, the number of ways to do this is $\dbinom{8}{2}-4$ . Then, there are two pairs and two nonmatching socks for you to pick from on Monday, a total of $6$ socks. Since you don't want to pick a pair, the number of ways to do this is $\dbinom{6}{2}-2$ . Thus the answer is $\dfrac{\left(5\right)\left(\dbinom{8}{2}-4\right)\left(\dbinom{6}{2}-2\right)}{\dbinom{10}{2}\dbinom{8}{2}\dbinom{6}{2}}=\dfrac{26}{315}.$ $26 + 315 = \boxed{341}$ .

Solution 3

For the first sock, note that to pick two different socks, can complementary count to get the total, $\binom{10}{2}$ minus the number of pairs (5) to get $\frac{\binom{10}{2} - 5}{\binom{10}{2}}$ The next steps aren't quite as simple, though. WLOG suppose the socks are (a, a, b, b, c, c, d, d, e, e) and that we chose ab on the first day. This leaves abccddee as the remaining socks. We can think of our next choice as how many "pairs" we "break". Note that right now, in abccddee there are 3 pairs, namely {cc, dd, ee}. Our next choice could either leave all of these pairs (if we choose ab), leave 2 of these pairs, (choose say ac to keep dd and ee as pairs), or leave only 1 as a pair, say choosing de to get abccde. $\bold{\text{Case 1: Break zero pairs}}.$ In this case, we want to keep 3 pairs remaining, so our only choice is to choose AB, which would make the remaining ccddee. The probability that we choose AB is $\frac{1}{\binom{8}{2}}$ and the probability that we get a pair after this is $\frac{3}{\binom{6}{2}}$ since we just choose CC, DD, or EE. This case has a probability $\frac{1}{\binom{8}{2}}\frac{3}{\binom{6}{2}}.$ $\bold{\text{Case 2: Break one pair}}.$ In this case, we want to choose A and one of {C,C,D,D,E,E} or B and one of {C,C,D,D,E,E}. This yields $\frac{6 + 6}{\binom{8}{2}}$ probability. After this, we end up with 2 pairs, so the total probability of choosing a pair on Wednesday in this case is $\frac{6 + 6}{\binom{8}{2}}\frac{2}{\binom{6}{2}}.$ $\bold{\text{case 3: Break 2 pairs}}.$ In this case we'd choose two distinct characters from {C,C,D,D,E,E} which would be $\frac{\binom{6}{2} - 3}{\binom{6}{2}}.$ After this, only one pair remains so the total probability for this case is

$\frac{\binom{6}{2} - 3}{\binom{6}{2}} \frac{6}{\binom{8}{2}}\frac{1}{\binom{6}{2}}.$ Adding all the cases and multiplying by $\frac{\binom{10}{2} - 5}{\binom{10}{2}}$ yields $\frac{\binom{10}{2} - 5}{\binom{10}{2}}\left(\frac{1}{\binom{8}{2}}\frac{3}{\binom{6}{2}}+\frac{6 + 6}{\binom{8}{2}}\frac{2}{\binom{6}{2}}+ \frac{\binom{6}{2} - 3}{\binom{6}{2}}\frac{6}{\binom{8}{2}}\frac{1}{\binom{6}{2}}\right) = \frac{26}{315} \rightarrow 26 + 315 = \boxed{341}$

@@ Line 3: / Line 3: @@
 In a drawer Sandy has <math>5</math> pairs of socks, each pair a different color.  On Monday Sandy selects two individual socks at random from the <math>10</math> socks in the drawer.  On Tuesday Sandy selects <math>2</math> of the remaining <math>8</math> socks at random and on Wednesday two of the remaining <math>6</math> socks at random.  The probability that Wednesday is the first day Sandy selects matching socks is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers,  Find <math>m+n</math>.
-==Hint==
+==Solution 1==
-Notice that we can allow the sample space of the problem to be the <math>\dfrac{10!}{(2!)^5}</math> possible permutations of socks, and that the desired outcomes are those for which the fifth and sixth items are the same color, the first and second are different colors, and the third and fourth are different colors.
+Let the fifth sock be arbitrary; the probability that the sixth sock matches in color is <math>\dfrac{1}{9}</math>.
-==Solution==
+Assuming this, then let the first sock be arbitrary; the probability that the second sock does not match is <math>\dfrac{6}{7}.</math>
-But this probability is simple to count. Let the fifth sock be arbitrary; the probability that the sixth sock matches in color is <math>\dfrac{1}{9}</math>. Let the first sock be arbitrary; the probability that the second sock does not match is <math>\dfrac{6}{7}.</math>
 The only "hard" part is the third and fourth sock. But that is simple casework. If the third sock's color matches the color of one of the first two socks (which occurs with probability <math>\dfrac{2}{6} = \dfrac{1}{3}</math>), then the fourth sock can be arbitrary. Otherwise (with probability <math>\dfrac{2}{3}</math>), the fourth sock can be chosen with probability <math>\dfrac{4}{5}</math> (5 socks left, 1 sock that can possibly match the third sock's color). The desired probability is thus
-<cmath>\frac{1}{9} \cdot \frac{6}{7} \cdot (\dfrac{1}{3} + \dfrac{2}{3} \cdot \dfrac{4}{5}) = \frac{26}{315}.</cmath>
+<cmath>\frac{1}{9} \cdot \frac{6}{7} \cdot \left(\dfrac{1}{3} + \dfrac{2}{3} \cdot \dfrac{4}{5}\right) = \frac{26}{315}.</cmath>
-The answer is <math>\dfrac{341}.</math>
+The sum is therefore <math>26+315=\boxed{341}.</math>
+==Solution 2==
+The key is to count backwards. First, choose the pair which you pick on Wednesday in <math>5</math> ways. Then there are four pairs of socks for you to pick a pair of on Tuesday, and you don't want to pick a pair. Since there are <math>4</math> pairs, the number of ways to do this is <math>\dbinom{8}{2}-4</math>. Then, there are two pairs and two nonmatching socks for you to pick from on Monday, a total of <math>6</math> socks. Since you don't want to pick a pair, the number of ways to do this is <math>\dbinom{6}{2}-2</math>. Thus the answer is
+<cmath>\dfrac{\left(5\right)\left(\dbinom{8}{2}-4\right)\left(\dbinom{6}{2}-2\right)}{\dbinom{10}{2}\dbinom{8}{2}\dbinom{6}{2}}=\dfrac{26}{315}.</cmath>
+<math>26 + 315 = \boxed{341}</math>.
+== Solution 3 ==
+For the first sock, note that to pick two different socks, can complementary count to get the total, <math>\binom{10}{2}</math> minus the number of pairs (5) to get <cmath>\frac{\binom{10}{2} - 5}{\binom{10}{2}}</cmath>
+The next steps aren't quite as simple, though.
+WLOG suppose the socks are (a, a, b, b, c, c, d, d, e, e) and that we chose ab on the first day.
+This leaves abccddee as the remaining socks. We can think of our next choice as how many "pairs" we "break".
+Note that right now, in abccddee there are 3 pairs, namely {cc, dd, ee}. Our next choice could either leave all of these pairs (if we choose ab), leave 2 of these pairs, (choose say ac to keep dd and ee as pairs), or leave only 1 as a pair, say choosing de to get abccde.
+<cmath>\bold{\text{Case 1: Break zero pairs}}.</cmath> In this case, we want to keep 3 pairs remaining, so our only choice is to choose AB, which would make the remaining ccddee. The probability that we choose AB is <math>\frac{1}{\binom{8}{2}}</math> and the probability that we get a pair after this is <math>\frac{3}{\binom{6}{2}}</math> since we just choose CC, DD, or EE. This case has a probability <math>\frac{1}{\binom{8}{2}}\frac{3}{\binom{6}{2}}.</math>
+<cmath>\bold{\text{Case 2: Break one pair}}.</cmath>
+In this case, we want to choose A and one of {C,C,D,D,E,E} or B and one of {C,C,D,D,E,E}. This yields <math>\frac{6 + 6}{\binom{8}{2}}</math> probability. After this, we end up with 2 pairs, so the total probability of choosing a pair on Wednesday in this case is <math>\frac{6 + 6}{\binom{8}{2}}\frac{2}{\binom{6}{2}}.</math>
+<cmath>\bold{\text{case 3: Break 2 pairs}}.</cmath>
+In this case we'd choose two distinct characters from {C,C,D,D,E,E} which would be <math>\frac{\binom{6}{2} - 3}{\binom{6}{2}}.</math> After this, only one pair remains so the total probability for this case is
+<math>\frac{\binom{6}{2} - 3}{\binom{6}{2}}    \frac{6}{\binom{8}{2}}\frac{1}{\binom{6}{2}}.</math>
+Adding all the cases and multiplying by <math>\frac{\binom{10}{2} - 5}{\binom{10}{2}}</math> yields
+<cmath>\frac{\binom{10}{2} - 5}{\binom{10}{2}}\left(\frac{1}{\binom{8}{2}}\frac{3}{\binom{6}{2}}+\frac{6 + 6}{\binom{8}{2}}\frac{2}{\binom{6}{2}}+ \frac{\binom{6}{2} - 3}{\binom{6}{2}}\frac{6}{\binom{8}{2}}\frac{1}{\binom{6}{2}}\right) = \frac{26}{315} \rightarrow 26 + 315 = \boxed{341}</cmath>
 == See also ==
 {{AIME box|year=2015|n=I|num-b=4|num-a=6}}
 {{MAA Notice}}
-[[Category:Introductory Geometry Problems]]
+[[Category:Introductory Combinatorics Problems]]

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

Page

Toolbox

Search