Difference between revisions of "2005 AIME II Problems/Problem 2"

Latest revision as of 10:28, 14 April 2024

Problem

A hotel packed breakfast for each of three guests. Each breakfast should have consisted of three types of rolls, one each of nut, cheese, and fruit rolls. The preparer wrapped each of the nine rolls and once wrapped, the rolls were indistinguishable from one another. She then randomly put three rolls in a bag for each of the guests. Given that the probability each guest got one roll of each type is $\frac mn,$ where $m$ and $n$ are relatively prime integers, find $m+n.$

Solution

Solution 1

Use construction. We need only calculate the probability the first and second person all get a roll of each type, since then the rolls for the third person are determined.

Person 1: $\frac{9 \cdot 6 \cdot 3}{9 \cdot 8 \cdot 7} = \frac{9}{28}$

Person 2: $\frac{6 \cdot 4 \cdot 2}{6 \cdot 5 \cdot 4} = \frac 25$
Person 3: One roll of each type is left, so the probability here is $1$ .

Our answer is thus $\frac{9}{28} \cdot \frac{2}{5} = \frac{9}{70}$ , and $m + n = \boxed{79}$ .

Solution 2

Call the three different types of rolls as A, B, and C. We need to arrange 3As, 3Bs, and 3Cs in a string such that A, B, and C appear in the first three, second three, and the third three like ABCABCABC or BCABACCAB. This can occur in $\left(\frac{3!}{1!1!1!}\right)^3 = 6^3 = 216$ different manners. The total number of possible strings is $\frac{9!}{3!3!3!} = 1680$ . The solution is therefore $\frac{216}{1680} = \frac{9}{70}$ , and $m + n = \boxed{79}$ .

Solution 3

The denominator of m/n is equal to the total amount of possible roll configurations given to the three people. This is equal to ${9 \choose 3}{6 \choose3}$ as the amount of ways to select three rolls out of 9 to give to the first person is ${9 \choose 3}$ , and three rolls out of 6 is ${6 \choose3}$ . After that, the three remaining rolls have no more configurations.

The numerator is the amount of ways to give one roll of each type to each of the three people, which can be done by defining the three types of rolls as x flavored, y flavored, and z flavored.

xxx, yyy, zzz

So you have to choose one x, one y, and one z to give to the first person. There are 3 xs, 3 ys, and 3 zs to select from, giving $3^3$ combinations. Multiply that by the combinations of xs, ys, and zs for the second person, which is evidently $2^3$ since there are two of each letter left.

$(27*8)/{9 \choose 3}{6 \choose3}$ simplifies down to our fraction m/n, which is $9/70$ . Adding them up gives $9 + 70 = \boxed{79}$ .

Solution 4

Let the objects be $A_1$ , $A_2$ , $A_3$ with similar labeling for $B$ and $C$ . There are $9!$ ways to order these nine objects in a line.

We then label three "zones" corresponding to the three people's meals as the first, second, and third objects in the line corresponding to the first zone, the fourth, fifth, and sixth to the second zone, and the remainder to the third zone. Each zone must contain one of each $A$ , $B$ , and $C$ . There are $6$ ways to place the three $A$ rolls in three different zones, and the same goes for $B$ and $C$ . In each zone, there are $6$ ways to order the three rolls, so there are in total $6^6$ legal orderings.

Thus the desired probability is $\frac{6^6}{9!}=\frac{9}{70}$ , so the answer is $9+70=\boxed{79}$ .

~eevee9406

@@ Line 1: / Line 1: @@
 == Problem ==
-A hotel packed breakfast for each of three guests. Each breakfast should have consisted of three types of rolls, one each of nut, cheese, and fruit rolls. The preparer wrapped each of the nine rolls and once wrapped, the rolls were indistinguishable from one another. She then randomly put three rolls in a bag for each of the guests. Given that the probability each guest got one roll of each type is <math> \frac mn, </math> where <math> m </math> and <math> n </math> are relatively prime integers, find <math> m+n. </math>
+A hotel packed breakfast for each of three guests. Each breakfast should have consisted of three types of rolls, one each of nut, cheese, and fruit rolls. The preparer wrapped each of the nine rolls and once wrapped, the rolls were indistinguishable from one another. She then randomly put three rolls in a bag for each of the guests. Given that the [[probability]] each guest got one roll of each type is <math> \frac mn, </math> where <math> m </math> and <math> n </math> are [[relatively prime]] [[integer]]s, find <math> m+n. </math>
+__TOC__
 == Solution ==
-{{solution}}
+=== Solution 1 ===
-== See Also ==
+Use [[construction]]. We need only calculate the probability the first and second person all get a roll of each type, since then the rolls for the third person are determined.
+*Person 1: <math>\frac{9 \cdot 6 \cdot 3}{9 \cdot 8 \cdot 7} = \frac{9}{28}</math>
+*Person 2: <math>\frac{6 \cdot 4 \cdot 2}{6 \cdot 5 \cdot 4} = \frac 25</math>
+*Person 3: One roll of each type is left, so the probability here is <math>1</math>.
+Our answer is thus <math>\frac{9}{28} \cdot \frac{2}{5} = \frac{9}{70}</math>, and <math>m + n = \boxed{79}</math>.
+=== Solution 2 ===
+Call the three different types of rolls as A, B, and C. We need to arrange 3As, 3Bs, and 3Cs in a string such that A, B, and C appear in the first three, second three, and the third three like ABCABCABC or BCABACCAB. This can occur in <math>\left(\frac{3!}{1!1!1!}\right)^3 = 6^3 = 216</math> different manners. The total number of possible strings is <math>\frac{9!}{3!3!3!} = 1680</math>. The solution is therefore <math>\frac{216}{1680} = \frac{9}{70}</math>, and <math>m + n = \boxed{79}</math>.
+===Solution 3===
+The denominator of m/n is equal to the total amount of possible roll configurations given to the three people. This is equal to <math>{9 \choose 3}{6 \choose3}</math> as the amount of ways to select three rolls out of 9 to give to the first person is <math>{9 \choose 3}</math>, and three rolls out of 6 is <math>{6 \choose3}</math>. After that, the three remaining rolls have no more configurations.
+The numerator is the amount of ways to give one roll of each type to each of the three people, which can be done by defining the three types of rolls as x flavored, y flavored, and z flavored.
+xxx, yyy, zzz
+So you have to choose one x, one y, and one z to give to the first person. There are 3 xs, 3 ys, and 3 zs to select from, giving <math>3^3</math> combinations. Multiply that by the combinations of xs, ys, and zs for the second person, which is evidently <math>2^3</math> since there are two of each letter left.
+<math>(27*8)/{9 \choose 3}{6 \choose3}</math> simplifies down to our fraction m/n, which is <math>9/70</math>. Adding them up gives <math>9 + 70 = \boxed{79}</math>.
+==Solution 4==
+Let the objects be <math>A_1</math>, <math>A_2</math>, <math>A_3</math> with similar labeling for <math>B</math> and <math>C</math>. There are <math>9!</math> ways to order these nine objects in a line.
+We then label three "zones" corresponding to the three people's meals as the first, second, and third objects in the line corresponding to the first zone, the fourth, fifth, and sixth to the second zone, and the remainder to the third zone. Each zone must contain one of each <math>A</math>, <math>B</math>, and <math>C</math>. There are <math>6</math> ways to place the three <math>A</math> rolls in three different zones, and the same goes for <math>B</math> and <math>C</math>. In each zone, there are <math>6</math> ways to order the three rolls, so there are in total <math>6^6</math> legal orderings.
+Thus the desired probability is <math>\frac{6^6}{9!}=\frac{9}{70}</math>, so the answer is <math>9+70=\boxed{79}</math>.
+~eevee9406
+== See also ==
+{{AIME  box|year=2005|n=II|num-b=1|num-a=3}}
-*[[2005 AIME II Problems/Problem 1| Previous problem]]
+[[Category:Intermediate Combinatorics Problems]]
-*[[2005 AIME II Problems/Problem 3| Next problem]]
+{{MAA Notice}}
-*[[2005 AIME II Problems]]

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

Page

Toolbox

Search