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 "2020 AMC 8 Problems/Problem 23"

(→‎Solution 2)
m (→‎Solution 3 (Complementary Counting))
 
(95 intermediate revisions by 44 users not shown)
Line 1: Line 1:
−
Five different awards are to be given to three students. Each student will receive at least one
+
==Problem==
−
award. In how many different ways can the awards be distributed?
+
Five different awards are to be given to three students. Each student will receive at least one award. In how many different ways can the awards be distributed?  
  
 
<math>\textbf{(A) }120 \qquad \textbf{(B) }150 \qquad \textbf{(C) }180 \qquad \textbf{(D) }210 \qquad \textbf{(E) }240</math>
 
<math>\textbf{(A) }120 \qquad \textbf{(B) }150 \qquad \textbf{(C) }180 \qquad \textbf{(D) }210 \qquad \textbf{(E) }240</math>
  
−
==Solution 1==
+
==Solution 1 (Constructive Counting)==
−
Credits to asbodke for the solution:
+
Firstly, observe that it is not possible for a single student to receive <math>4</math> or <math>5</math> awards because this would mean that one of the other students receives no awards. Thus, each student must receive either <math>1</math>, <math>2</math>, or <math>3</math> awards. If a student receives <math>3</math> awards, then the other two students must each receive <math>1</math> award; if a student receives <math>2</math> awards, then another student must also receive <math>2</math> awards and the remaining student must receive <math>1</math> award. We consider each of these two cases in turn.
−
Without the restriction that each student receives one award, the answer is <math>3^5=243</math>. We then subtract the cases where one student doesn't receive an award. There are 3 students to choose from, and then after that, there are <math>2^5=32</math> options, so we subtract <math>3\cdot32=96</math> options. However, the cases where one student receives the awards were counted once originally, but then subtracted twice! However, we only want them to be counted zero times, so we have to add them back again. There are 3 cases when this happens (since there are 3 students). Thus, the answer is <math>243-96+3=150\implies\boxed{\textbf{(B)}150}</math>.
 
  
−
==Solution 2==
+
If a student receives three awards, there are <math>3</math> ways to choose which student this is, and <math>\binom{5}{3}</math> ways to give that student <math>3</math> out of the <math>5</math> awards. Next, there are <math>2</math> students left and <math>2</math> awards to give out, with each student getting one award. There are clearly just <math>2</math> ways to distribute these two awards out, giving <math>3\cdot\binom{5}{3}\cdot 2=60</math> ways to distribute the awards in this case.
−
First, observe that it is not possible for a single student to receive four or five awards because this would mean that one of the other students receives no awards. Thus, each student must receive either one, two, or three awards. If a student receives three awards, then the other two students must each receive one award. If a student receives two awards, then another student must also receive two awards, and the remaining student must receive one award. Thus, there are only two cases to consider.
+
 
−
<br><br>
+
In the other case, two students receive <math>2</math> awards and one student recieves <math>1</math> award . We know there are <math>3</math> choices for which student gets <math>1</math> award. There are <math>\binom{3}{1}</math> ways to do this. Then, there are <math>\binom{5}{2}</math> ways to give the first student his two awards, leaving <math>3</math> awards yet to distribute. There are then <math>\binom{3}{2}</math> ways to give the second student his <math>2</math> awards. Finally, there is only <math>1</math> student and <math>1</math> award left, so there is only <math>1</math> way to distribute this award. This results in <math>\binom{5}{2}\cdot\binom{3}{2}\cdot 1\cdot 3 =90</math> ways to distribute the awards in this case. Adding the results of these two cases, we get <math>60+90=\boxed{\textbf{(B) }150}</math>.
−
Case 1: A student receives three awards
+
 
−
First we have to choose which of the three students we will select to give three awards to. There are 3 ways to do this. There are <math>\binom{5}{3}</math> ways to give that student three of the five awards. Next, there are two students left and two awards to give out, with each student getting one award. There are 2 ways to give these two awards out. This results in <math>3\cdot\binom{5}{3}\cdot 2=60</math> ways to distribute the awards in this case.
+
==Solution 2 (Casework) ==
−
<br><br>
+
 
−
Case 2: A student receives two awards
+
Upon inspection (specified in the above solution), there are two cases of the distribution of awards to the students: one student gets 3 awards and the other each get 1 award or one student gets 1 award and the other two get 2 awards.
−
First we have to choose which of the two students we will select to give two awards each to. There are <math>\binom{3}{2}</math> ways to do this. There are <math>\binom{5}{2}</math> ways to give the first student his two awards, leaving 3 awards yet to distribute. There are <math>\binom{3}{2}</math> ways to give the second student his two awards. Finally, there is only one student and one award left so there is only one way to distribute this award. This results in <math>\binom{3}{2}\cdot\binom{5}{2}\cdot\binom{3}{2}\cdot 1=90</math> ways to distribute the awards in this case.
+
 
−
<br><br>
+
 
−
Adding the results of these two cases, we get <math>60+90=150 \implies\boxed{\textbf{(B)}150}</math>.
+
In the first case, there are <math>\binom{3}{1} = 3</math> ways to choose the person who gets 3 awards. From here, there are <math>\binom{5}{3} = 10</math> ways to choose the 3 awards from the 5 total awards. Now, one person has <math>2</math> choices for awards and the other has <math>1</math> choice for the award. Thus, the total number of ways to choose awards in this case is <math>3 \cdot 10 \cdot 2 \cdot 1 = 60</math>.
−
~jmansuri
+
 
 +
 
 +
In the other case, there are <math>\binom{3}{1} = 3</math> ways to choose the person who gets 1 award, and <math>5</math> choices for his/her award. Then, one person has <math>\binom{4}{2} = 6</math> ways to have his/her awards and the other person has <math>\dbinom{2}{2} = 1</math> ways to have his/her awards. This gives <math>3 \cdot 5 \cdot 6 \cdot 1  = 90</math> ways for this case.
 +
 
 +
Adding these cases together, we get <math>60 + 90 = 150</math> ways to distribute the awards, or choice <math>\boxed{\textbf{(B) }150}</math>.
 +
 
 +
==Solution 3 (Complementary Counting)==
 +
 
 +
Without the restriction that each student receives at least one award, we could take each of the awards and choose one of the <math>3</math> students to give it to. This would be <math>3^5</math> ways to distribute the awards in total. Now we need to subtract the cases where at least one student doesn't receive an award. If a student doesn't receive an award, there are <math>3</math> choices for which student that is, so <math>2^5</math> ways of choosing a student to receive each of the awards; in total, <math>3\cdot32=96</math>.
 +
 
 +
However, if <math>2</math> students both don't receive an award, then this case would be counted twice among the <math>96</math>, so we need to add back in these cases. Said in other words, <math>2</math> students not receiving an award is equivalent to <math>1</math> student receiving <math>5</math> awards, and there are <math>3</math> choices for whom that student would be. To finish, the total number of ways to distribute the awards is <math>243 - 96+3</math>, or <math>\boxed{\textbf{(B) }150}</math>.
 +
 
 +
==Video Solution by Math-X (First understand the problem!!!)==
 +
https://youtu.be/UnVo6jZ3Wnk?si=aB0A9Rb1KMIxOcpQ&t=5070
 +
 
 +
~Math-X
 +
 
 +
==Video Solution (🚀Under 3 min🚀)==
 +
https://youtu.be/0CWA2KWvAXY
 +
 
 +
==Video Solution==
 +
https://youtu.be/3mMfy_evxl4
 +
 
 +
Please like and subscribe!
 +
 
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/dFFjlxm43b0?t=899
 +
 
 +
~ pi_is_3.14
 +
 
 +
==Video Solution by SpreadTheMathLove==
 +
https://www.youtube.com/watch?v=Dg_2wXNY3tE
 +
 
 +
==Video Solution by WhyMath==
 +
https://youtu.be/HkFQe7ZxBb4
 +
 
 +
~WhyMath
 +
 
 +
==Video Solutions by The Learning Royal==
 +
https://youtu.be/tDChKU0pVN4
 +
 
 +
https://youtu.be/RUg6QfV5yg4
 +
 
 +
==Video Solution by Interstigation==
 +
https://youtu.be/YnwkBZTv5Fw?t=1443
 +
 
 +
~Interstigation
 +
 
 +
==Video Solution by STEMbreezy==
 +
https://youtu.be/wq8EUCe5oQU?t=243
 +
 
 +
~STEMbreezy
  
 
==See also==  
 
==See also==  
 
{{AMC8 box|year=2020|num-b=22|num-a=24}}
 
{{AMC8 box|year=2020|num-b=22|num-a=24}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Introductory Combinatorics Problems]]

Latest revision as of 20:31, 14 January 2024

Problem

Five different awards are to be given to three students. Each student will receive at least one award. In how many different ways can the awards be distributed?

$\textbf{(A) }120 \qquad \textbf{(B) }150 \qquad \textbf{(C) }180 \qquad \textbf{(D) }210 \qquad \textbf{(E) }240$

Solution 1 (Constructive Counting)

Firstly, observe that it is not possible for a single student to receive $4$ or $5$ awards because this would mean that one of the other students receives no awards. Thus, each student must receive either $1$, $2$, or $3$ awards. If a student receives $3$ awards, then the other two students must each receive $1$ award; if a student receives $2$ awards, then another student must also receive $2$ awards and the remaining student must receive $1$ award. We consider each of these two cases in turn.

If a student receives three awards, there are $3$ ways to choose which student this is, and $\binom{5}{3}$ ways to give that student $3$ out of the $5$ awards. Next, there are $2$ students left and $2$ awards to give out, with each student getting one award. There are clearly just $2$ ways to distribute these two awards out, giving $3\cdot\binom{5}{3}\cdot 2=60$ ways to distribute the awards in this case.

In the other case, two students receive $2$ awards and one student recieves $1$ award . We know there are $3$ choices for which student gets $1$ award. There are $\binom{3}{1}$ ways to do this. Then, there are $\binom{5}{2}$ ways to give the first student his two awards, leaving $3$ awards yet to distribute. There are then $\binom{3}{2}$ ways to give the second student his $2$ awards. Finally, there is only $1$ student and $1$ award left, so there is only $1$ way to distribute this award. This results in $\binom{5}{2}\cdot\binom{3}{2}\cdot 1\cdot 3 =90$ ways to distribute the awards in this case. Adding the results of these two cases, we get $60+90=\boxed{\textbf{(B) }150}$.

Solution 2 (Casework)

Upon inspection (specified in the above solution), there are two cases of the distribution of awards to the students: one student gets 3 awards and the other each get 1 award or one student gets 1 award and the other two get 2 awards.


In the first case, there are $\binom{3}{1} = 3$ ways to choose the person who gets 3 awards. From here, there are $\binom{5}{3} = 10$ ways to choose the 3 awards from the 5 total awards. Now, one person has $2$ choices for awards and the other has $1$ choice for the award. Thus, the total number of ways to choose awards in this case is $3 \cdot 10 \cdot 2 \cdot 1 = 60$.


In the other case, there are $\binom{3}{1} = 3$ ways to choose the person who gets 1 award, and $5$ choices for his/her award. Then, one person has $\binom{4}{2} = 6$ ways to have his/her awards and the other person has $\dbinom{2}{2} = 1$ ways to have his/her awards. This gives $3 \cdot 5 \cdot 6 \cdot 1 = 90$ ways for this case.

Adding these cases together, we get $60 + 90 = 150$ ways to distribute the awards, or choice $\boxed{\textbf{(B) }150}$.

Solution 3 (Complementary Counting)

Without the restriction that each student receives at least one award, we could take each of the awards and choose one of the $3$ students to give it to. This would be $3^5$ ways to distribute the awards in total. Now we need to subtract the cases where at least one student doesn't receive an award. If a student doesn't receive an award, there are $3$ choices for which student that is, so $2^5$ ways of choosing a student to receive each of the awards; in total, $3\cdot32=96$.

However, if $2$ students both don't receive an award, then this case would be counted twice among the $96$, so we need to add back in these cases. Said in other words, $2$ students not receiving an award is equivalent to $1$ student receiving $5$ awards, and there are $3$ choices for whom that student would be. To finish, the total number of ways to distribute the awards is $243 - 96+3$, or $\boxed{\textbf{(B) }150}$.

Video Solution by Math-X (First understand the problem!!!)

https://youtu.be/UnVo6jZ3Wnk?si=aB0A9Rb1KMIxOcpQ&t=5070

~Math-X

Video Solution (🚀Under 3 min🚀)

https://youtu.be/0CWA2KWvAXY

Video Solution

https://youtu.be/3mMfy_evxl4

Please like and subscribe!

Video Solution by OmegaLearn

https://youtu.be/dFFjlxm43b0?t=899

~ pi_is_3.14

Video Solution by SpreadTheMathLove

https://www.youtube.com/watch?v=Dg_2wXNY3tE

Video Solution by WhyMath

https://youtu.be/HkFQe7ZxBb4

~WhyMath

Video Solutions by The Learning Royal

https://youtu.be/tDChKU0pVN4

https://youtu.be/RUg6QfV5yg4

Video Solution by Interstigation

https://youtu.be/YnwkBZTv5Fw?t=1443

~Interstigation

Video Solution by STEMbreezy

https://youtu.be/wq8EUCe5oQU?t=243

~STEMbreezy

See also

2020 AMC 8 (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
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 AJHSME/AMC 8 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=2020_AMC_8_Problems/Problem_23&oldid=210759"