Difference between revisions of "2019 AIME I Problems/Problem 4"
m (→Solution 2 (Casework)) |
Prism melody (talk | contribs) (→Solution 2 (Casework)) |
||
(14 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
A soccer team has <math>22</math> available players. A fixed set of <math>11</math> players starts the game, while the other <math>11</math> are available as substitutes. During the game, the coach may make as many as <math>3</math> substitutions, where any one of the <math>11</math> players in the game is replaced by one of the substitutes. No player removed from the game may reenter the game, although a substitute entering the game may be replaced later. No two substitutions can happen at the same time. The players involved and the order of the substitutions matter. Let <math>n</math> be the number of ways the coach can make substitutions during the game (including the possibility of making no substitutions). Find the remainder when <math>n</math> is divided by <math>1000</math>. | A soccer team has <math>22</math> available players. A fixed set of <math>11</math> players starts the game, while the other <math>11</math> are available as substitutes. During the game, the coach may make as many as <math>3</math> substitutions, where any one of the <math>11</math> players in the game is replaced by one of the substitutes. No player removed from the game may reenter the game, although a substitute entering the game may be replaced later. No two substitutions can happen at the same time. The players involved and the order of the substitutions matter. Let <math>n</math> be the number of ways the coach can make substitutions during the game (including the possibility of making no substitutions). Find the remainder when <math>n</math> is divided by <math>1000</math>. | ||
==Solution 1 (Recursion)== | ==Solution 1 (Recursion)== | ||
− | There are <math>0-3</math> substitutions. The number of ways to sub any number of times must be multiplied by the previous number. This is defined recursively. The case for 0 subs is 1, and the ways to reorganize after <math>n</math> subs is the product of the number of new subs (<math>12-n</math>) and the players that can be ejected (<math>11</math>). The formula for <math>n</math> subs is then <math>a_n=11(12-n)a_{n-1}</math> with <math>a_0=1</math>. | + | There are <math>0-3</math> substitutions. The number of ways to sub any number of times must be multiplied by the previous number. This is defined recursively. The case for <math>0</math> subs is <math>1</math>, and the ways to reorganize after <math>n</math> subs is the product of the number of new subs (<math>12-n</math>) and the players that can be ejected (<math>11</math>). The formula for <math>n</math> subs is then <math>a_n=11(12-n)a_{n-1}</math> with <math>a_0=1</math>. |
− | Summing from 0 to 3 gives <math>1+11^2+11^{3}10+11^{4}10\ | + | Summing from <math>0</math> to <math>3</math> gives <math>1+11^2+11^{3}\cdot 10+11^{4}\cdot 10\cdot 9</math>. Notice that <math>10+9\cdot11\cdot10=10+990=1000</math>. Then, rearrange it into <math>1+11^2+11^3\cdot (10+11\cdot10\cdot9)= 1+11^2+11^3\cdot (1000)</math>. When taking modulo <math>1000</math>, the last term goes away. What is left is <math>1+11^2=\boxed{122}</math>. |
~BJHHar | ~BJHHar | ||
Line 12: | Line 12: | ||
We can perform casework. Call the substitution area the "bench". | We can perform casework. Call the substitution area the "bench". | ||
− | Case 1: No substitutions. There is <math>1</math> way of doing this: leaving everybody on the field. | + | <math>\textbf{Case 1}</math>: No substitutions. There is <math>1</math> way of doing this: leaving everybody on the field. |
− | Case 2: One substitution. Choose one player on the field to sub out, and one player on the bench. This corresponds to <math>11\cdot 11 = 121</math>. | + | <math>\textbf{Case 2}</math>: One substitution. Choose one player on the field to sub out, and one player on the bench. This corresponds to <math>11\cdot 11 = 121</math>. |
− | Case 3: Two substitutions. Choose one player on the field to sub out, and one player on the bench. Once again, this is <math>11\cdot 11</math>. Now choose one more player on the field to sub out and one player on the bench that was not the original player subbed out. This gives us a total of <math>11\cdot 11\cdot 11\cdot 10 = 13310\equiv 310 \bmod{ | + | <math>\textbf{Case 3}</math>: Two substitutions. Choose one player on the field to sub out, and one player on the bench. Once again, this is <math>11\cdot 11</math>. Now choose one more player on the field to sub out and one player on the bench that was not the original player subbed out. This gives us a total of <math>11\cdot 11\cdot 11\cdot 10 = 13310\equiv 310 \bmod{1000}</math>. |
− | Case 4: Three substitutions. Using similar logic as Case 3, we get <math>(11\cdot 11)\cdot (11\cdot 10)\cdot (11\cdot 9)</math>. The resulting number ends in <math>690</math>. | + | <math>\textbf{Case 4}</math>: Three substitutions. Using similar logic as <math>\textbf{Case 3}</math>, we get <math>(11\cdot 11)\cdot (11\cdot 10)\cdot (11\cdot 9)</math>. The resulting number ends in <math>690</math>. |
− | Therefore, the answer is <math>1 + 121 + 310 + 690 | + | Therefore, the answer is <math>1 + 121 + 310 + 690 \equiv \boxed{122} \pmod{1000}</math>. |
+ | |||
+ | ~minor mistake fixed by [[User:Prism_melody|Prism Melody]] | ||
+ | |||
+ | ==Solution 3 (Official MAA)== | ||
+ | There is <math>1</math> way of making no substitutions to the starting lineup. If the coach makes exactly one substitution, this can be done in <math>11^2</math> ways. Two substitutions can happen in <math>11^2\cdot11\cdot 10</math> ways. Similarly, three substitutions can happen <math>11^2\cdot11\cdot10\cdot11\cdot9</math> ways. The total number of possibilities is <math>1+11^2+11^2\cdot11\cdot10+11^2\cdot11\cdot10\cdot11\cdot9=122+11^3(10+990)\equiv 122\pmod{1000}.</math> | ||
+ | |||
+ | ==Video Solution #1(A bit of casework, a bit of counting)== | ||
+ | https://youtu.be/JQdad7APQG8?t=981 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/I-8xZGhoDUY | ||
+ | |||
+ | ~Shreyas S | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2019|n=I|num-b=3|num-a=5}} | {{AIME box|year=2019|n=I|num-b=3|num-a=5}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 10:32, 5 February 2022
Contents
Problem
A soccer team has available players. A fixed set of
players starts the game, while the other
are available as substitutes. During the game, the coach may make as many as
substitutions, where any one of the
players in the game is replaced by one of the substitutes. No player removed from the game may reenter the game, although a substitute entering the game may be replaced later. No two substitutions can happen at the same time. The players involved and the order of the substitutions matter. Let
be the number of ways the coach can make substitutions during the game (including the possibility of making no substitutions). Find the remainder when
is divided by
.
Solution 1 (Recursion)
There are substitutions. The number of ways to sub any number of times must be multiplied by the previous number. This is defined recursively. The case for
subs is
, and the ways to reorganize after
subs is the product of the number of new subs (
) and the players that can be ejected (
). The formula for
subs is then
with
.
Summing from to
gives
. Notice that
. Then, rearrange it into
. When taking modulo
, the last term goes away. What is left is
.
~BJHHar
Solution 2 (Casework)
We can perform casework. Call the substitution area the "bench".
: No substitutions. There is
way of doing this: leaving everybody on the field.
: One substitution. Choose one player on the field to sub out, and one player on the bench. This corresponds to
.
: Two substitutions. Choose one player on the field to sub out, and one player on the bench. Once again, this is
. Now choose one more player on the field to sub out and one player on the bench that was not the original player subbed out. This gives us a total of
.
: Three substitutions. Using similar logic as
, we get
. The resulting number ends in
.
Therefore, the answer is .
~minor mistake fixed by Prism Melody
Solution 3 (Official MAA)
There is way of making no substitutions to the starting lineup. If the coach makes exactly one substitution, this can be done in
ways. Two substitutions can happen in
ways. Similarly, three substitutions can happen
ways. The total number of possibilities is
Video Solution #1(A bit of casework, a bit of counting)
https://youtu.be/JQdad7APQG8?t=981
Video Solution
~Shreyas S
See Also
2019 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.