Difference between revisions of "2021 AMC 10B Problems/Problem 22"
(→Solution 3) |
(→Solution 3) |
||
Line 36: | Line 36: | ||
<cmath>f_5=T_5 -{\binom{5}{1}\binom{5}{1} f_4 - \binom{5}{2}\binom{5}{2}2!f_3 - \binom{5}{3}\binom{5}{3}3!f_2 - 5!}</cmath> | <cmath>f_5=T_5 -{\binom{5}{1}\binom{5}{1} f_4 - \binom{5}{2}\binom{5}{2}2!f_3 - \binom{5}{3}\binom{5}{3}3!f_2 - 5!}</cmath> | ||
− | In case b), there are <math>\binom{5}{2}</math> ways to choose 2 boxes that | + | In case b), there are <math>\binom{5}{2}</math> ways to choose 2 boxes that have the same color, <math>\binom{5}{2}</math> ways to choose the two colors, 2! ways to permute the 2 chosen colors, and <math>f_3</math> ways so that the remaining 3 boxes don’t have the same color. The same goes for cases a) and c). In case e), the total number of ways to permute 5 colors is <math>5!</math>. |
− | <math>f_2=T_2-2 = (2!)^3 - 2 = 6</math>, since we subtract the number of cases where the boxes contain uniform colors, which is 2. | + | We have <math>f_2=T_2-2 = (2!)^3 - 2 = 6</math>, since we subtract the number of cases where the boxes contain uniform colors, which is 2. |
− | <math>f_3=T_3-\Big[3!+ \binom{3}{1}\binom{3}{1}\cdot f_2 \Big] = 156 </math> - again, we must subtract the ways where boxes have uniform colors. If all 3 boxes have the same color, there are <math>3!</math> ways to permute them. If one box has the same color, there are <math>\binom{3}{1}</math> ways to pick a box, and <math>\binom{3}{1}</math> ways to pick a color for that box. There is 1! ways to rearrange the color in the box. The remaining boxes must have different colors, so we multiply by <math>f_2</math>. | + | In the same way, <math>f_3=T_3-\Big[3!+ \binom{3}{1}\binom{3}{1}\cdot f_2 \Big] = 156 </math> - again, we must subtract the ways where boxes have uniform colors. If all 3 boxes have the same color, there are <math>3!</math> ways to permute them. If one box has the same color, there are <math>\binom{3}{1}</math> ways to pick a box, and <math>\binom{3}{1}</math> ways to pick a color for that box. There is 1! ways to rearrange the color in the box. The remaining boxes must have different colors, so we multiply by <math>f_2</math>. Similarly, |
<math>f_4=(4!)^3-\Big[ 4!+ \binom{4}{2}\binom{4}{2}\cdot 2! \cdot f_2+ \binom{4}{1}\binom{4}{1}\cdot f_3\Big] = 10,872</math> | <math>f_4=(4!)^3-\Big[ 4!+ \binom{4}{2}\binom{4}{2}\cdot 2! \cdot f_2+ \binom{4}{1}\binom{4}{1}\cdot f_3\Big] = 10,872</math> |
Revision as of 18:42, 21 February 2021
Contents
Problem
Ang, Ben, and Jasmin each have blocks, colored red, blue, yellow, white, and green; and there are
empty boxes. Each of the people randomly and independently of the other two people places one of their blocks into each box. The probability that at least one box receives
blocks all of the same color is
, where
and
are relatively prime positive integers. What is
Solution
Let our denominator be , so we consider all possible distributions.
We use PIE (Principle of Inclusion and Exclusion) to count the successful ones.
When we have at box with all
balls the same color in that box, there are
ways for the distributions to occur (
for selecting one of the five boxes for a uniform color,
for choosing the color for that box,
for each of the three people to place their remaining items).
However, we overcounted those distributions where two boxes had uniform color, and there are ways for the distributions to occur (
for selecting two of the five boxes for a uniform color,
for choosing the color for those boxes,
for each of the three people to place their remaining items).
Again, we need to re-add back in the distributions with three boxes of uniform color... and so on so forth.
Our success by PIE is
yielding an answer of
.
Solution 2
As In Solution 1, the probability is
Dividing by
, we get
Dividing by
, we get
Dividing by
, we get
.
Solution 3
Use complimentary counting.
Denote as the total number of ways to put n colors to n boxes by 3 people out of which
ways are such that no box has uniform color. Notice
. From this setup we see the question is asking for
. To find
we want to exclude the cases of a) one box of the same color, b) 2 boxes of the same color, c) 3 boxes of same color, d) 4 boxes of the same color, and e) 5 boxes of the same color. Cases d) and e) coincide. From this, we have
In case b), there are ways to choose 2 boxes that have the same color,
ways to choose the two colors, 2! ways to permute the 2 chosen colors, and
ways so that the remaining 3 boxes don’t have the same color. The same goes for cases a) and c). In case e), the total number of ways to permute 5 colors is
.
We have , since we subtract the number of cases where the boxes contain uniform colors, which is 2.
In the same way, - again, we must subtract the ways where boxes have uniform colors. If all 3 boxes have the same color, there are
ways to permute them. If one box has the same color, there are
ways to pick a box, and
ways to pick a color for that box. There is 1! ways to rearrange the color in the box. The remaining boxes must have different colors, so we multiply by
. Similarly,
Thus,
Thus, the probability is and the answer is
Video Solution by OmegaLearn (Principal of Inclusion Exclusion)
~ pi_is_3.14
Video Solution by Interstigation
~ Briefly went over Principal of Inclusion Exclusion using Venn Diagram
2021 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |