Difference between revisions of "2020 AMC 8 Problems/Problem 23"
(→Video Solutions) |
|||
(23 intermediate revisions by 7 users not shown) | |||
Line 5: | Line 5: | ||
<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 (complementary counting)== |
Without the restriction that each student receives at least one award, we could simply take each of the <math>5</math> awards and choose one of the <math>3</math> students to give it to, so that there would be <math>3^5=243</math> ways to distribute the awards. We now 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, then <math>2^5 = 32</math> ways of choosing a student to receive each of the awards, for a total of <math>3 \cdot 32 = 96</math>. However, if <math>2</math> students both don't receive an award, then such a case would be counted twice among our <math>96</math>, so we need to add back in these cases. Of course, <math>2</math> students both not receiving an award is equivalent to only <math>1</math> student receiving all <math>5</math> awards, so there are simply <math>3</math> choices for which student that would be. It follows that the total number of ways of distributing the awards is <math>243-96+3=\boxed{\textbf{(B) }150}</math>. | Without the restriction that each student receives at least one award, we could simply take each of the <math>5</math> awards and choose one of the <math>3</math> students to give it to, so that there would be <math>3^5=243</math> ways to distribute the awards. We now 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, then <math>2^5 = 32</math> ways of choosing a student to receive each of the awards, for a total of <math>3 \cdot 32 = 96</math>. However, if <math>2</math> students both don't receive an award, then such a case would be counted twice among our <math>96</math>, so we need to add back in these cases. Of course, <math>2</math> students both not receiving an award is equivalent to only <math>1</math> student receiving all <math>5</math> awards, so there are simply <math>3</math> choices for which student that would be. It follows that the total number of ways of distributing the awards is <math>243-96+3=\boxed{\textbf{(B) }150}</math>. | ||
Line 11: | Line 11: | ||
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. 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. | 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. 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. | ||
− | In the other case, a student receives <math>2</math> awards. We first have to choose which of the | + | In the other case, a student receives <math>2</math> awards. We first have to choose which of the three students we will select to give two awards each to. There are <math>\binom{3}{2}</math> ways to do this, after which 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{3}{2}\cdot\binom{5}{2}\cdot\binom{3}{2}\cdot 1=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>. |
==Solution 3 (variation of Solution 2)== | ==Solution 3 (variation of Solution 2)== | ||
If each student must receive at least one award, then, as in Solution 2, we deduce that the only possible ways to split up the <math>5</math> awards are <math>3,1,1</math> and <math>2,2,1</math> (i.e. one student gets three awards and the others get one each, or two students each get two awards and the other student is left with the last one). In the first case, there are <math>3</math> choices for which student gets <math>3</math> awards, and <math>\binom{5}{3} = 10</math> choices for which <math>3</math> awards they get. We are then left with <math>2</math> awards, and there are exactly <math>2</math> choices depending on which remaining student gets which. This yields a total for this case of <math>3 \cdot 10 \cdot 2 = 60</math>. For the second case, there are similarly <math>3</math> choices for which student gets only <math>1</math> award, and <math>5</math> choices for which award he gets. There are then <math>4</math> remaining awards, from which we choose <math>2</math> to give to one student and <math>2</math> to give to the other, which can be done in <math>\binom{4}{2} = 6</math> ways (and we can say that e.g. the <math>2</math> chosen this way go to the first remaining student and the other <math>2</math> go to the second remaining student, which counts all possibilities). This means the total for the second case is <math>3 \cdot 5 \cdot 6 = 90</math>, and the answer is <math>60 + 90 = \boxed{\textbf{(B) }150}</math>. | If each student must receive at least one award, then, as in Solution 2, we deduce that the only possible ways to split up the <math>5</math> awards are <math>3,1,1</math> and <math>2,2,1</math> (i.e. one student gets three awards and the others get one each, or two students each get two awards and the other student is left with the last one). In the first case, there are <math>3</math> choices for which student gets <math>3</math> awards, and <math>\binom{5}{3} = 10</math> choices for which <math>3</math> awards they get. We are then left with <math>2</math> awards, and there are exactly <math>2</math> choices depending on which remaining student gets which. This yields a total for this case of <math>3 \cdot 10 \cdot 2 = 60</math>. For the second case, there are similarly <math>3</math> choices for which student gets only <math>1</math> award, and <math>5</math> choices for which award he gets. There are then <math>4</math> remaining awards, from which we choose <math>2</math> to give to one student and <math>2</math> to give to the other, which can be done in <math>\binom{4}{2} = 6</math> ways (and we can say that e.g. the <math>2</math> chosen this way go to the first remaining student and the other <math>2</math> go to the second remaining student, which counts all possibilities). This means the total for the second case is <math>3 \cdot 5 \cdot 6 = 90</math>, and the answer is <math>60 + 90 = \boxed{\textbf{(B) }150}</math>. | ||
− | ==Video | + | ==Video Solutions== |
− | https://youtu.be/ | + | https://youtu.be/tDChKU0pVN4 <br /> |
− | + | https://youtu.be/RUg6QfV5yg4 | |
− | |||
==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}} |
Latest revision as of 18:54, 6 January 2021
Contents
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?
Solution 1 (complementary counting)
Without the restriction that each student receives at least one award, we could simply take each of the awards and choose one of the students to give it to, so that there would be ways to distribute the awards. We now 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 choices for which student that is, then ways of choosing a student to receive each of the awards, for a total of . However, if students both don't receive an award, then such a case would be counted twice among our , so we need to add back in these cases. Of course, students both not receiving an award is equivalent to only student receiving all awards, so there are simply choices for which student that would be. It follows that the total number of ways of distributing the awards is .
Solution 2
Firstly, observe that it is not possible for a single student to receive or awards because this would mean that one of the other students receives no awards. Thus, each student must receive either , , or awards. If a student receives awards, then the other two students must each receive award; if a student receives awards, then another student must also receive awards and the remaining student must receive award. We consider each of these two cases in turn. If a student receives three awards, there are ways to choose which student this is, and ways to give that student out of the awards. Next, there are students left and awards to give out, with each student getting one award. There are clearly just ways to distribute these two awards out, giving ways to distribute the awards in this case.
In the other case, a student receives awards. We first have to choose which of the three students we will select to give two awards each to. There are ways to do this, after which there are ways to give the first student his two awards, leaving awards yet to distribute. There are then ways to give the second student his awards. Finally, there is only student and award left, so there is only way to distribute this award. This results in ways to distribute the awards in this case. Adding the results of these two cases, we get .
Solution 3 (variation of Solution 2)
If each student must receive at least one award, then, as in Solution 2, we deduce that the only possible ways to split up the awards are and (i.e. one student gets three awards and the others get one each, or two students each get two awards and the other student is left with the last one). In the first case, there are choices for which student gets awards, and choices for which awards they get. We are then left with awards, and there are exactly choices depending on which remaining student gets which. This yields a total for this case of . For the second case, there are similarly choices for which student gets only award, and choices for which award he gets. There are then remaining awards, from which we choose to give to one student and to give to the other, which can be done in ways (and we can say that e.g. the chosen this way go to the first remaining student and the other go to the second remaining student, which counts all possibilities). This means the total for the second case is , and the answer is .
Video Solutions
https://youtu.be/tDChKU0pVN4
https://youtu.be/RUg6QfV5yg4
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.