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 "2021 AMC 10B Problems/Problem 22"
(→‎Solution 3)
Line 32: Line 32:
 
== Solution 3 ==  
 
== Solution 3 ==  
 
Use complimentary counting.  
 
Use complimentary counting.  
−
Denote <math>f_n</math> 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 <math>1-\frac{f_5}{(5!)^3}</math>. To find <math>f_5</math> 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
+
Denote <math>T_n</math> as the total number of ways to put n colors to n boxes by 3 people out of which <math>f_n</math> ways are such that no box has uniform color. Notice <math>T_n = (n!)^3</math>. From this setup we see the question is asking for <math>1-\frac{f_5}{(5!)^3}</math>. To find <math>f_5</math> 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 e) 5 boxes of the same color. Cases d) and e) coincide. From this, we have
 +
 
 
<cmath>f_5=(5!)^3-{\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=(5!)^3-{\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>
  
−
Take for example, case b). There are <math>\binom{5}{2}</math> ways to choose 2 boxes that will have the same color, <math>\binom{5}{2}</math> ways to choose that color, 2! ways to permute the 2 chosen colors, and <math>f_3</math> ways so that the remaining boxes don’t have the same color. The same goes for the rest of the cases.
+
In case b), there are <math>\binom{5}{2}</math> ways to choose 2 boxes that will have the same color, <math>\binom{5}{2}</math> ways to choose that color, 2! ways to permute the 2 chosen colors, and <math>f_3</math> ways so that the remaining boxes don’t have the same color. The same goes for cases a) and c). In case e), the total number of ways is <math>5!</math>.  
  
−
Going back to <math>f_5</math>, there are exactly <math>(5!)^3</math> 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.
+
Going back to <math>f_5</math>, there are exactly <math>(5!)^3</math> 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 <math>f_2, f_3 and f_4</math>.
−
Now, we just need to calculate <math>f_2,f_3,f_4</math>.
 
  
−
<math>f_2=(2!)^3-2 = 6</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.  
−
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.  
 
  
−
<math>f_3=(3!)^3-[3!+ \binom{3}{1}\binom{3}{1}2f_2] = 216 - [6 + 9\cdot6] = 156 </math>
+
<math>f_3=T_3-[3!+ \binom{3}{1}\binom{3}{1}\cdot f_2] = 216 - [6 + 9\cdot 6] = 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>
−
For <math>f_3</math>, There are <math>(3!)^3</math> 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 <math>3!</math> ways for the colors to be rearranged. 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>
 
  
−
<math>f_4=(4!)^3-[4!+ \binom{4}{2}\binom{4}{2} 2! f_2+ \binom{4}{1}\binom{4}{1}*f_3] = 13824 - [24+ 36*2*6 + 16*156] = 10,872</math>
+
<math>f_4=(4!)^3-[4!+ \binom{4}{2}\binom{4}{2}\cdot 2! \cdot f_2+ \binom{4}{1}\binom{4}{1}\cdot f_3] = 13824 - [24 + 36\cdot 2 \cdot 6 + 16 \cdot 156] = 10,872</math>
  
−
Thus, <math>f_5 = f_5=(5!)^3-{\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!} = (5!)^3 - [25*10,872 + 100*2*156 + 100*6*6 + 120] = (5!)^3 - 306,720</math>
+
Thus, <math>f_5 = f_5=(5!)^3-{\binom{5}{1}\binom{5}{1}\cdot f_4+ \binom{5}{2}\binom{5}{2}\cdot 2!\cdot f_3+\binom{5}{3}\binom{5}{3}\cdot 3!\cdot f_2 + 5!} = (5!)^3 - [25\cdot 10,872 + 100\cdot 2\cdot 156 + 100\cdot 6\cdot 6 + 120] = (5!)^3 - 306,720</math>
  
−
Thus, the probability is <cmath>1 - \frac{(5!)^3 - 306,720}{(5!)^3} = 71/400</cmath>
+
Thus, the probability is <math>1 - \frac{(5!)^3 - 306,720}{(5!)^3} = 71/400 and the answer is \boxed{\textbf{(D) }471}</math>
−
<cmath>\boxed{\textbf{(D) }471}</cmath>
 
  
 
== Video Solution by OmegaLearn (Principal of Inclusion Exclusion) ==
 
== Video Solution by OmegaLearn (Principal of Inclusion Exclusion) ==

Revision as of 17:22, 21 February 2021

Problem

Ang, Ben, and Jasmin each have $5$ blocks, colored red, blue, yellow, white, and green; and there are $5$ 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 $3$ blocks all of the same color is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. What is $m + n ?$

$\textbf{(A)} ~47 \qquad\textbf{(B)} ~94 \qquad\textbf{(C)} ~227 \qquad\textbf{(D)} ~471 \qquad\textbf{(E)} ~542$

Solution

Let our denominator be $(5!)^3$, so we consider all possible distributions.

We use PIE (Principle of Inclusion and Exclusion) to count the successful ones.

When we have at $1$ box with all $3$ balls the same color in that box, there are $_{5} C _{1} \cdot _{5} P _{1} \cdot (4!)^3$ ways for the distributions to occur ($_{5} C _{1}$ for selecting one of the five boxes for a uniform color, $_{5} P _{1}$ for choosing the color for that box, $4!$ 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 $_{5} C _{2} \cdot _{5} P _{2} \cdot (3!)^3$ ways for the distributions to occur ($_{5} C _{2}$ for selecting two of the five boxes for a uniform color, $_{5} P _{2}$ for choosing the color for those boxes, $3!$ 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.\] \[\frac{120 \cdot 2556}{120^3}=\frac{71}{400},\] yielding an answer of $\boxed{471 \textbf{(D)}}$.

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}\] \[= \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}.\] Dividing by $5!$, we get \[\frac{5\cdot (4!)^2 - 10\cdot (3!)^2 + 10\cdot (2!)^2 - 5 + 1}{(5!)^2}.\] Dividing by $4$, we get \[\frac{5\cdot 6\cdot 24 - 10\cdot 9 + 10 - 1}{30\cdot 120}.\] Dividing by $9$, we get \[\frac{5\cdot 2\cdot 8 - 10 + 1}{10\cdot 40} = \frac{71}{400} \implies \boxed{\textbf{(D) }471}\].


Solution 3

Use complimentary counting. Denote $T_n$ as the total number of ways to put n colors to n boxes by 3 people out of which $f_n$ ways are such that no box has uniform color. Notice $T_n = (n!)^3$. From this setup we see the question is asking for $1-\frac{f_5}{(5!)^3}$. To find $f_5$ 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 e) 5 boxes of the same color. Cases d) and e) coincide. From this, we have

\[f_5=(5!)^3-{\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!}\]

In case b), there are $\binom{5}{2}$ ways to choose 2 boxes that will have the same color, $\binom{5}{2}$ ways to choose that color, 2! ways to permute the 2 chosen colors, and $f_3$ ways so that the remaining boxes don’t have the same color. The same goes for cases a) and c). In case e), the total number of ways is $5!$.

Going back to $f_5$, there are exactly $(5!)^3$ 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, f_3 and f_4$.

$f_2=T_2-2 = (2!)^3 - 2 = 6$, since we subtract the number of cases where the boxes contain uniform colors, which is 2.

$f_3=T_3-[3!+ \binom{3}{1}\binom{3}{1}\cdot f_2] = 216 - [6 + 9\cdot 6] = 156$ - again, we must subtract the ways where boxes have uniform colors. If all 3 boxes have the same color, there are $3!$ ways to permute them. If one box has the same color, there are $\binom{3}{1}$ ways to pick a box, and $\binom{3}{1}$ 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_2$

$f_4=(4!)^3-[4!+ \binom{4}{2}\binom{4}{2}\cdot 2! \cdot f_2+ \binom{4}{1}\binom{4}{1}\cdot f_3] = 13824 - [24 + 36\cdot 2 \cdot 6 + 16 \cdot 156] = 10,872$

Thus, $f_5 = f_5=(5!)^3-{\binom{5}{1}\binom{5}{1}\cdot f_4+ \binom{5}{2}\binom{5}{2}\cdot 2!\cdot f_3+\binom{5}{3}\binom{5}{3}\cdot 3!\cdot f_2 + 5!} = (5!)^3 - [25\cdot 10,872 + 100\cdot 2\cdot 156 + 100\cdot 6\cdot 6 + 120] = (5!)^3 - 306,720$

Thus, the probability is $1 - \frac{(5!)^3 - 306,720}{(5!)^3} = 71/400 and the answer is \boxed{\textbf{(D) }471}$

Video Solution by OmegaLearn (Principal of Inclusion Exclusion)

https://youtu.be/o0S8SqRO0Yc

~ pi_is_3.14


Video Solution by Interstigation

https://youtu.be/OVW9KhmmrVQ

~ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AMC_10B_Problems/Problem_22&oldid=147677"