Difference between revisions of "2019 AIME I Problems/Problem 4"
m (→Problem 4) |
|||
| Line 2: | Line 2: | ||
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== | + | ==Solution 1 (Recursion)== |
| + | There can be 0-3 substitutions. The number of ways for one number of subs must also be multiplied by the number of ways for the previous. This can be defined recursively. The case for 0 subs is just 1, and the number of ways to reorganize a team after <math>n</math> subs is the produce of the possible new subs <math>12-n</math> and the number of 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\cdot9</math>. Notice that <math>10+9\cdot11\cdot10=1000</math>. Then, rearrange it into <math>1+11^2+11^3(10+11\cdot9)=1+11^2+11^3(1000)</math>. In the context of the problem, the last term goes away when taking modulo 1000, so the answer is <math>1+11^2=\boxed{122}</math> | ||
| + | |||
| + | |||
| + | |||
| + | ~BJHHar | ||
| + | |||
| + | ==Solution 2 (Casework) == | ||
We can perform casework. Call the substitution area the "bench". | We can perform casework. Call the substitution area the "bench". | ||
Case 1: No substitutions. 1. | Case 1: No substitutions. 1. | ||
| Line 11: | Line 20: | ||
Case 4: Three substitutions. Using similar logic as with Case 3 we get (11 * 11) * (11 * 10) * (11 * 9) which ends in 690, so the answer is 1 + 121 + 1000 = <math>\boxed{122}</math>. | Case 4: Three substitutions. Using similar logic as with Case 3 we get (11 * 11) * (11 * 10) * (11 * 9) which ends in 690, so the answer is 1 + 121 + 1000 = <math>\boxed{122}</math>. | ||
| + | |||
==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}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Revision as of 19:37, 29 September 2019
Problem 4
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 can be 0-3 substitutions. The number of ways for one number of subs must also be multiplied by the number of ways for the previous. This can be defined recursively. The case for 0 subs is just 1, and the number of ways to reorganize a team after subs is the produce of the possible new subs 
and the number of players that can be ejected . The formula for subs is then 
with 
.
Summing from 0 to 3 gives 
. Notice that 
. Then, rearrange it into 
. In the context of the problem, the last term goes away when taking modulo 1000, so the answer is 
~BJHHar
Solution 2 (Casework)
We can perform casework. Call the substitution area the "bench". Case 1: No substitutions. 1.
Case 2: One substitution. Choose one player on the field to sub out, and one player on the bench = 11 * 11 = 121.
Case 3: Two substitutions. Choose one player on the field to sub out, and one player on the bench = 11 * 11 so far. Now choose one player on the field to sub out, and one player on the bench that was not the original player subbed out = * 11 * 10 = 13310 = 310.
Case 4: Three substitutions. Using similar logic as with Case 3 we get (11 * 11) * (11 * 10) * (11 * 9) which ends in 690, so the answer is 1 + 121 + 1000 = 
.
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. 
