2021 AMC 10B Problems/Problem 22
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 ![\[_{5} C _{1} \cdot _{5} P _{1} \cdot (4!)^3 - _{5} C _{2} \cdot _{5} P _{2} \cdot (3!)^3 + _{5} C _{3} \cdot _{5} P _{3} \cdot (2!)^3 - _{5} C _{4} \cdot _{5} P _{4} \cdot (1!)^3 + _{5} C _{5} \cdot _{5} P _{5} \cdot (0!)^3 = 120 \cdot 2556.\]](http://latex.artofproblemsolving.com/a/5/9/a59888bd1785744fa33e206eac015cdc07be6a66.png)
![\[\frac{120 \cdot 2556}{120^3}=\frac{71}{400},\]](http://latex.artofproblemsolving.com/e/8/7/e87883620d06649fc386896ce567597f3e0fcbbd.png)
yielding an answer of 
.
Solution 2
As In Solution 1, the probability is
![\[\frac{\binom{5}{1}\cdot 5\cdot (4!)^3 - \binom{5}{2}\cdot 5\cdot 4\cdot (3!)^3 + \binom{5}{3}\cdot 5\cdot 4\cdot 3\cdot (2!)^3 - \binom{5}{4}\cdot 5\cdot 4\cdot 3\cdot 2\cdot (1!)^3 + \binom{5}{5}\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(5!)^3}\]](http://latex.artofproblemsolving.com/6/4/0/640a3a5d7dfd279790c235824f0057b02ce5a21a.png)
![\[= \frac{5\cdot 5\cdot (4!)^3 - 10\cdot 5\cdot 4\cdot (3!)^3 + 10\cdot 5\cdot 4\cdot 3\cdot (2!)^3 - 5\cdot 5! + 5!}{(5!)^3}.\]](http://latex.artofproblemsolving.com/8/8/6/886ae9b2d024da35824d6243bd1a4a51b419496e.png)
Dividing by 
, we get
![\[\frac{5\cdot (4!)^2 - 10\cdot (3!)^2 + 10\cdot (2!)^2 - 5 + 1}{(5!)^2}.\]](http://latex.artofproblemsolving.com/a/8/4/a84faefead4a5c5085f958b05057f8b5270995fc.png)
Dividing by 
, we get
![\[\frac{5\cdot 6\cdot 24 - 10\cdot 9 + 10 - 1}{30\cdot 120}.\]](http://latex.artofproblemsolving.com/2/a/2/2a2f3e12cac556b615e7654c5c3de3888a4d6c31.png)
Dividing by 
, we get
![\[\frac{5\cdot 2\cdot 8 - 10 + 1}{10\cdot 40} = \frac{71}{400} \implies \boxed{\textbf{(D) }471}\]](http://latex.artofproblemsolving.com/3/8/2/382e1db842bb7fa792e7f7d50494f7e0dcd0b66d.png)
.
Solution 3
Use complimentary counting.
Denote 
as the number of ways to put n colors to n boxes by 3 people such that no box has uniform color. From this setup we see the question is asking for ![\[1-\frac{f_5}{(5!)^3}\]](http://latex.artofproblemsolving.com/9/f/7/9f72a02c724452be241ef81ddd34da9f6f4154c9.png)
. To find 
we want to exclude the cases of a) one box of the same color b) 2 boxes of the same color and so forth. From this, we have
![\[f_5=(5!)^3-{\binom{5}{1}^2 f_4+ \binom{5}{2}^22!f_3+\binom{5}{3}^23!f_2+5!}\]](http://latex.artofproblemsolving.com/a/8/2/a8248db9a032b8774d7b47d26444c62d474a965b.png)
Take for example, case b). There are 
ways to choose 2 boxes that will have the same color, ways to choose that color, 2! ways to permute the 2 chosen colors, and 
ways so that the remaining boxes don’t have the same color. The same goes for the rest of the cases.
Going back to , there are exactly ways for 3 people to rearrange the 5 colors, but we wish to subtract the cases where at least 1 box has the same color.
Now, we just need to calculate 
![\[f_2=(2!)^3-2 = 6\]](http://latex.artofproblemsolving.com/6/8/9/6892a4e134b5b37f4e8bcc0abd3678d1bf378f22.png)
There are (2!)^3 ways to rearrange colors, but we must subtract the cases where the boxes contain uniform colors. There are 2 ways to do that.
![\[f_3=(3!)^3-[3!+ \binom{3}{1}^2f_2] = 216 - [6 + 9\cdot6] = 156\]](http://latex.artofproblemsolving.com/8/d/4/8d448812a01a0b61d02074fd2872d0fe8f510d68.png)
For , There are 
ways to rearrange the colors, but we must subtract the ways where boxes have uniform colors. If all 3 boxes have the same color, there are ways for the colors to be rearranged. 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 
![\[f_4=(4!)^3-[4!+ \binom{4}{2}^2 2! f_2+ \binom{4}{1}^2*f_3] = 13824 - [24+ 36*2*6 + 16*156] = 10,872\]](http://latex.artofproblemsolving.com/b/d/e/bde25b9829ee6ba0e868b6988a010bd60ccd41af.png)
Thus, ![\[f_5 = f_5=(5!)^3-{\binom{5}{1}^2 f_4+ \binom{5}{2}^2 2!f_3+\binom{5}{3}^23!f_2+5!} = (5!)^3 - [25*10,872 + 100*2*156 + 100*6*6 + 120] = (5!)^3 - 306,720\]](http://latex.artofproblemsolving.com/9/8/8/98878e2730b82d0fc2956b47587f357e4f146ac2.png)
Thus, the probability is ![\[1 - \frac{(5!)^3 - 306,720}{(5!)^3} = 71/400\]](http://latex.artofproblemsolving.com/d/1/1/d1195329ae26b1a99d2f0eea59656d6fa6c43802.png)
![\[\boxed{\textbf{(D) }471}\]](http://latex.artofproblemsolving.com/0/a/c/0acf2ca09e477df62401b2d2fedb0b41cb04d046.png)
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 | ||
