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

2019 AIME I Problems/Problem 4

Revision as of 19:41, 29 September 2019 by Bjhhar (talk | contribs) (→‎Solution 1 (Recursion))

Problem 4

A soccer team has $22$ available players. A fixed set of $11$ players starts the game, while the other $11$ are available as substitutes. During the game, the coach may make as many as $3$ substitutions, where any one of the $11$ 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 $n$ be the number of ways the coach can make substitutions during the game (including the possibility of making no substitutions). Find the remainder when $n$ is divided by $1000$.

Solution 1 (Recursion)

There are 0-3 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 $n$ subs is the product of the number of new subs ($12-n$) and the players that can be ejected ($11$). The formula for $n$ subs is then $a_n=11(12-n)a_{n-1}$ with $a_0=1$.


Summing from 0 to 3 gives $1+11^2+11^{3}10+11^{4}10\cdot9$. Notice that $10+9\cdot11\cdot10=10+990=1000$. Then, rearrange it into $1+11^2+11^3(10+11\cdot9)=1+11^2+11^3(1000)$.When taking modulo 1000, the last term goes away. What is left is $1+11^2=\boxed{122}$

~Whoof~

~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 = $\boxed{122}$.


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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_4&oldid=110060"