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 "2018 AIME I Problems/Problem 3"
(→‎Problem)
 
(33 intermediate revisions by 22 users not shown)
Line 1: Line 1:
−
==Question==
+
==Problem==
−
Kathy has \(5\) red cards and \(5\) green cards. She shuffles the \(10\) cards and lays out \(5\) of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders \(RRGGG, GGGGR,\) or \(RRRRR\) will make Kathy happy, but \(RRRGR\) will not. The probability that Kathy will be happy is \( \dfrac{m}{n}\), where \(m\) and \(n\) are relatively prime positive integers. Find \(m + n\).
+
Cathy has <math>5</math> red cards and <math>5</math> green cards. She shuffles the <math>10</math> cards and lays out <math>5</math> of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders RRGGG, GGGGR, or RRRRR will make Cathy happy, but RRRGR will not. The probability that Kathy will be happy is <math> \frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n</math>    .
  
 +
==Solution 1==
  
−
==Solution==
+
We have <math>2+4\cdot 2</math> cases total.
−
Light work
 
−
 
 
−
 
 
−
You have <math>2+4\cdot 2</math> cases total.
 
  
 
The two are all red and all green. Then, you have 4 of one, 1 of other. 3 of one, 2 of other. 2 of one, 3 of other. 1 of one, 4 of other. Then flip the order, so times two.
 
The two are all red and all green. Then, you have 4 of one, 1 of other. 3 of one, 2 of other. 2 of one, 3 of other. 1 of one, 4 of other. Then flip the order, so times two.
Line 23: Line 20:
 
For the 1 and 4, we have: <cmath>5\cdot 5\cdot 4\cdot 3\cdot 2.</cmath>
 
For the 1 and 4, we have: <cmath>5\cdot 5\cdot 4\cdot 3\cdot 2.</cmath>
  
−
Adding up and remembering to double the last four cases, since they can be reversed, we get, after simplifying: <cmath>\boxed{\dfrac{31}{126}}.</cmath>
+
Adding up and remembering to double all of them, since they can be reversed and the 5's can be red or green, we get, after simplifying: <math>\dfrac{31}{126}</math>
 +
 
 +
Thus the answer is <math>31 + 126 = \boxed{157}</math>.
 +
-gorefeebuddie
 +
 
 +
==Solution 2==
 +
 
 +
Our probability will be <math>\dfrac{\text{number of "happy" configurations of cards}}{\text{total number of configurations of cards}}.</math>
 +
 
 +
First of all, we have <math>10</math> choices for the first card, <math>9</math> choices for the second card, <math>8</math> choices for the third card, <math>7</math> choices for the fourth card, and <math>6</math> choices for the last card. This gives a total of <math>10\cdot 9\cdot 8\cdot 7\cdot 6</math> possible ways for five cards to be chosen.
 +
 
 +
Finding the number of configurations that make Kathy happy is a more difficult task, however, and we will resort to casework to do it.
 +
 
 +
First, let's look at the appearances of the "happy configurations" that Kathy likes. Based on the premise of the problem, we can realize that there are ten cases for the appearance of the configurations: <cmath>\text{RRRRR},</cmath> <cmath>\text{GGGGG},</cmath> <cmath>\text{RRRRG},</cmath> <cmath>\text{GGGGR},</cmath> <cmath>\text{RRRGG},</cmath> <cmath>\text{GGGRR},</cmath> <cmath>\text{RRGGG},</cmath> <cmath>\text{GGRRR},</cmath> <cmath>\text{RGGGG},</cmath> <cmath>\text{GRRRR}.</cmath> But this doesn't mean there are 10 "happy configurations" in total-- remember that we've been treating these cards as distinguishable, so we must continue to do so.
 +
 
 +
To lighten the load of 10 cases on the human brain, we can note that in the eyes of what we will soon do, <math>RRRRR</math> and <math>GGGGG</math> are effectively equivalent, and therefore may be treated in the same case. We will have to multiply by 2 at the end, though.
 +
 
 +
Similarly, we can equate <math>RRRRG,</math> <math>GGGGR,</math> <math>RGGGG,</math> and <math>GRRRR,</math> as well as <math>RRRGG,</math> <math>GGGRR,</math> <math>RRGGG,</math> and <math>GGRRR,</math> so that we just have three cases. We can approach each of these cases with constructive counting.
 +
 
 +
Case 1: <math>RRRRR</math>-type.
 +
 
 +
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>1</math> for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 1=120</math> configurations for this case. There are <math>2</math> cases of this type.
 +
 +
Case 2: <math>RRRRG</math>-type.
 +
 
 +
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>2</math> for the fourth card, and <math>5</math> choices for the last card (not <math>1</math>, because we're doing a new color). This leads to a total of <math>5\cdot 4\cdot 3\cdot 2\cdot 5=600</math> configurations for this case. There are <math>4</math> cases of this type.
 +
 
 +
Case 3: <math>RRRGG</math>-type.
 +
 
 +
For this case, there are <math>5</math> available choices for the first card, <math>4</math> available choices for the second card, <math>3</math> for the third card, <math>5</math> for the fourth card, and <math>4</math> choices for the last card. This leads to a total of <math>5\cdot 4\cdot 3\cdot 5\cdot 4=1200</math> configurations for this case. There are <math>4</math> cases of this type.
 +
 
 +
Adding the cases up gives <math>2\cdot 120+4\cdot 600+4\cdot 1200=7440</math> "happy" configurations in total.
 +
 
 +
This means that the probability that Kathy is happy will be <math>\dfrac{7440}{10\cdot 9\cdot 8\cdot 7\cdot 6},</math> which simplifies to <math>\dfrac{31}{126}.</math>
 +
 
 +
So the answer is <math>31+126=\boxed{157}</math>
 +
 
 +
==Solution 3==
 +
As the problem states, some examples of valid are <math>RRGGG</math>, <math>GGGGR</math>, and <math>RRRRR</math>. Let's use each of these as more general cases.
 +
 
 +
Let <math>RRGGG</math> be the case when there are 2 adjacents of one color, and 3 adjacents of the other color. This yields <math>4</math> combinations (<math>RRGGG</math>, <math>GGRRR</math>, <math>RRRGG</math>, and <math>GGGRR</math>). The probability of each of these is equal, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{5}{8}\cdot \frac{4}{7}\cdot \frac{3}{6}=\frac{5}{126}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{126}=\frac{10}{63}</math>
 +
 
 +
Next case is <math>GGGGR</math>. Let this be when there are 4 adjacents of one color, and 1 individual color. Once again, this yields <math>4</math> combinations (<math>GGGGR</math>, <math>RRRRG</math>, <math>RGGGG</math>, and <math>GRRRR</math>). The probability of each is the same, equating to <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{5}{6}=\frac{5}{252}</math>, and since there are <math>4</math> combinations, the probability of this case is <math>4\cdot \frac{5}{252}=\frac{5}{63}</math>
 +
 
 +
The final case is <math>RRRRR</math>, in which there is just an adjacent block of <math>5</math> colors. There are only <math>2</math> combinations this time, each equating to the probability <math>\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{1}{6}=\frac{1}{252}</math>, and since there are <math>2</math> combinations, the probability of this case is <math>2\cdot \frac{1}{252}=\frac{1}{126}</math>.
 +
 
 +
Thus, the total probability is <math>\frac{10}{63}+\frac{5}{63}+\frac{1}{126}=\frac{31}{126} \implies m+n=\boxed{157}</math>
 +
 
 +
==Solution 4==
 +
Kathy will draw the 10 cards in some order, but the restriction of having all greens in a row and all reds in a row only applies to the first 5 cards drawn. The total number of ways the 10 cards can be drawn is simply 10 choose 5 which is 252. Now we just count the number of possible successful configurations of the ten cards. The first 5 cards can start either be <math>GRRRR</math>, <math>GGRRR</math>, <math>GGGRR</math>, <math>GGGGR</math>, <math>GGGGG</math> or the same thing except starting with a red. The number of ways to order <math>GRRRR</math> is the number of ways to order the last 5 cards, which is 5C1. Doing all of the other cases, the total is <math>(\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5})*2 = 62</math>. <math>\frac{62}{252} = \frac{31}{126},</math> so the solution is <math> 31 + 126 = \boxed{157}</math>
 +
 
 +
-bradleyguo
 +
<br>
 +
Minor LaTeX edits by fasterthanlight
 +
 
 +
==Solution 5==
 +
Suppose <math>k</math> of the first <math>5</math> cards are red. There are <math>\binom{5}{k}</math> ways to order the last five cards, and either <math>1</math> or <math>2</math> ways to order the first five cards: <math>1</math> if <math>k=0</math> or <math>k=5</math>, otherwise <math>2</math>. So, the number of orderings that work is
 +
<cmath>\binom{5}{0} + 2\binom{5}{1} + 2\binom{5}{2} + 2\binom{5}{3} + 2\binom{5}{4} + \binom{5}{5} = 2\sum_{k=0}^{5}\binom{5}{k} - 2 = 2^6 - 2.</cmath>
 +
 
 +
The total number of orderings is <math>\binom{10}{5} = 252,</math> so the answer is <math>\frac{62}{252} = \boxed{\frac{31}{126}}</math>
 +
 
 +
==Solution 6 (Official MAA)==
 +
Assume without loss of generality that the first card laid out is red. Then the arrangements that satisfy Kathy’s requirements are RRRRR, RRRRG, RRRGG, RRGGG, and RGGGG. The probability that Kathy will lay out one of these
 +
arrangements is <cmath>\frac49\cdot\frac38\cdot\frac27\cdot\frac16</cmath> <cmath>\frac49\cdot\frac38\cdot\frac27\cdot\frac56</cmath> <cmath>\frac49\cdot\frac38\cdot\frac57\cdot\frac46</cmath> <cmath>\frac49\cdot\frac58\cdot\frac47\cdot\frac36</cmath> <cmath>+\frac59\cdot\frac48\cdot\frac37\cdot\frac26</cmath> <cmath>\overline{..........................}</cmath> <cmath>\frac{31}{126}</cmath> The requested sum is <math>31+126=\boxed{157}.</math>
 +
 
 +
==Video Solution==
 +
 
 +
https://www.youtube.com/watch?v=WVtbD8x9fCM
 +
~Shreyas S
 +
 
 +
==See Also==
 +
{{AIME box|year=2018|n=I|num-b=2|num-a=4}}
 +
{{MAA Notice}}

Latest revision as of 04:09, 10 September 2024

Problem

Cathy has $5$ red cards and $5$ green cards. She shuffles the $10$ cards and lays out $5$ of the cards in a row in a random order. She will be happy if and only if all the red cards laid out are adjacent and all the green cards laid out are adjacent. For example, card orders RRGGG, GGGGR, or RRRRR will make Cathy happy, but RRRGR will not. The probability that Kathy will be happy is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

Solution 1

We have $2+4\cdot 2$ cases total.

The two are all red and all green. Then, you have 4 of one, 1 of other. 3 of one, 2 of other. 2 of one, 3 of other. 1 of one, 4 of other. Then flip the order, so times two.

Obviously the denominator is $10\cdot 9\cdot 8\cdot 7\cdot 6$, since we are choosing a card without replacement.

Then, we have for the numerator for the two of all red and green: \[5\cdot 4\cdot 3\cdot 2\cdot 1.\]

For the 4 and 1, we have: \[5\cdot 4\cdot 3\cdot 2\cdot 5.\]

For the 3 and 2, we have: \[5\cdot 4\cdot 3\cdot 5\cdot 4.\]

For the 2 and 3, we have: \[5\cdot 4\cdot 5\cdot 4\cdot 3.\]

For the 1 and 4, we have: \[5\cdot 5\cdot 4\cdot 3\cdot 2.\]

Adding up and remembering to double all of them, since they can be reversed and the 5's can be red or green, we get, after simplifying: $\dfrac{31}{126}$

Thus the answer is $31 + 126 = \boxed{157}$. -gorefeebuddie

Solution 2

Our probability will be $\dfrac{\text{number of "happy" configurations of cards}}{\text{total number of configurations of cards}}.$

First of all, we have $10$ choices for the first card, $9$ choices for the second card, $8$ choices for the third card, $7$ choices for the fourth card, and $6$ choices for the last card. This gives a total of $10\cdot 9\cdot 8\cdot 7\cdot 6$ possible ways for five cards to be chosen.

Finding the number of configurations that make Kathy happy is a more difficult task, however, and we will resort to casework to do it.

First, let's look at the appearances of the "happy configurations" that Kathy likes. Based on the premise of the problem, we can realize that there are ten cases for the appearance of the configurations: \[\text{RRRRR},\] \[\text{GGGGG},\] \[\text{RRRRG},\] \[\text{GGGGR},\] \[\text{RRRGG},\] \[\text{GGGRR},\] \[\text{RRGGG},\] \[\text{GGRRR},\] \[\text{RGGGG},\] \[\text{GRRRR}.\] But this doesn't mean there are 10 "happy configurations" in total-- remember that we've been treating these cards as distinguishable, so we must continue to do so.

To lighten the load of 10 cases on the human brain, we can note that in the eyes of what we will soon do, $RRRRR$ and $GGGGG$ are effectively equivalent, and therefore may be treated in the same case. We will have to multiply by 2 at the end, though.

Similarly, we can equate $RRRRG,$ $GGGGR,$ $RGGGG,$ and $GRRRR,$ as well as $RRRGG,$ $GGGRR,$ $RRGGG,$ and $GGRRR,$ so that we just have three cases. We can approach each of these cases with constructive counting.

Case 1: $RRRRR$-type.

For this case, there are $5$ available choices for the first card, $4$ available choices for the second card, $3$ for the third card, $2$ for the fourth card, and $1$ for the last card. This leads to a total of $5\cdot 4\cdot 3\cdot 2\cdot 1=120$ configurations for this case. There are $2$ cases of this type.

Case 2: $RRRRG$-type.

For this case, there are $5$ available choices for the first card, $4$ available choices for the second card, $3$ for the third card, $2$ for the fourth card, and $5$ choices for the last card (not $1$, because we're doing a new color). This leads to a total of $5\cdot 4\cdot 3\cdot 2\cdot 5=600$ configurations for this case. There are $4$ cases of this type.

Case 3: $RRRGG$-type.

For this case, there are $5$ available choices for the first card, $4$ available choices for the second card, $3$ for the third card, $5$ for the fourth card, and $4$ choices for the last card. This leads to a total of $5\cdot 4\cdot 3\cdot 5\cdot 4=1200$ configurations for this case. There are $4$ cases of this type.

Adding the cases up gives $2\cdot 120+4\cdot 600+4\cdot 1200=7440$ "happy" configurations in total.

This means that the probability that Kathy is happy will be $\dfrac{7440}{10\cdot 9\cdot 8\cdot 7\cdot 6},$ which simplifies to $\dfrac{31}{126}.$

So the answer is $31+126=\boxed{157}$

Solution 3

As the problem states, some examples of valid are $RRGGG$, $GGGGR$, and $RRRRR$. Let's use each of these as more general cases.

Let $RRGGG$ be the case when there are 2 adjacents of one color, and 3 adjacents of the other color. This yields $4$ combinations ($RRGGG$, $GGRRR$, $RRRGG$, and $GGGRR$). The probability of each of these is equal, equating to $\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{5}{8}\cdot \frac{4}{7}\cdot \frac{3}{6}=\frac{5}{126}$, and since there are $4$ combinations, the probability of this case is $4\cdot \frac{5}{126}=\frac{10}{63}$

Next case is $GGGGR$. Let this be when there are 4 adjacents of one color, and 1 individual color. Once again, this yields $4$ combinations ($GGGGR$, $RRRRG$, $RGGGG$, and $GRRRR$). The probability of each is the same, equating to $\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{5}{6}=\frac{5}{252}$, and since there are $4$ combinations, the probability of this case is $4\cdot \frac{5}{252}=\frac{5}{63}$

The final case is $RRRRR$, in which there is just an adjacent block of $5$ colors. There are only $2$ combinations this time, each equating to the probability $\frac{5}{10}\cdot \frac{4}{9}\cdot \frac{3}{8}\cdot \frac{2}{7}\cdot \frac{1}{6}=\frac{1}{252}$, and since there are $2$ combinations, the probability of this case is $2\cdot \frac{1}{252}=\frac{1}{126}$.

Thus, the total probability is $\frac{10}{63}+\frac{5}{63}+\frac{1}{126}=\frac{31}{126} \implies m+n=\boxed{157}$

Solution 4

Kathy will draw the 10 cards in some order, but the restriction of having all greens in a row and all reds in a row only applies to the first 5 cards drawn. The total number of ways the 10 cards can be drawn is simply 10 choose 5 which is 252. Now we just count the number of possible successful configurations of the ten cards. The first 5 cards can start either be $GRRRR$, $GGRRR$, $GGGRR$, $GGGGR$, $GGGGG$ or the same thing except starting with a red. The number of ways to order $GRRRR$ is the number of ways to order the last 5 cards, which is 5C1. Doing all of the other cases, the total is $(\binom{5}{1}+\binom{5}{2}+\binom{5}{3}+\binom{5}{4}+\binom{5}{5})*2 = 62$. $\frac{62}{252} = \frac{31}{126},$ so the solution is $31 + 126 = \boxed{157}$

-bradleyguo
Minor LaTeX edits by fasterthanlight

Solution 5

Suppose $k$ of the first $5$ cards are red. There are $\binom{5}{k}$ ways to order the last five cards, and either $1$ or $2$ ways to order the first five cards: $1$ if $k=0$ or $k=5$, otherwise $2$. So, the number of orderings that work is \[\binom{5}{0} + 2\binom{5}{1} + 2\binom{5}{2} + 2\binom{5}{3} + 2\binom{5}{4} + \binom{5}{5} = 2\sum_{k=0}^{5}\binom{5}{k} - 2 = 2^6 - 2.\]

The total number of orderings is $\binom{10}{5} = 252,$ so the answer is $\frac{62}{252} = \boxed{\frac{31}{126}}$

Solution 6 (Official MAA)

Assume without loss of generality that the first card laid out is red. Then the arrangements that satisfy Kathy’s requirements are RRRRR, RRRRG, RRRGG, RRGGG, and RGGGG. The probability that Kathy will lay out one of these arrangements is \[\frac49\cdot\frac38\cdot\frac27\cdot\frac16\] \[\frac49\cdot\frac38\cdot\frac27\cdot\frac56\] \[\frac49\cdot\frac38\cdot\frac57\cdot\frac46\] \[\frac49\cdot\frac58\cdot\frac47\cdot\frac36\] \[+\frac59\cdot\frac48\cdot\frac37\cdot\frac26\] \[\overline{..........................}\] \[\frac{31}{126}\] The requested sum is $31+126=\boxed{157}.$

Video Solution

https://www.youtube.com/watch?v=WVtbD8x9fCM ~Shreyas S

See Also

2018 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
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=2018_AIME_I_Problems/Problem_3&oldid=226879"