Question

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.$

Answer

Solution:

At every moment there are $11$ players in the game, any of whom may be removed, while the bench shrinks by one with each substitution. So the first substitution can be made in $11 \cdot 11$ ways, the second in $11 \cdot 10$ ways, and the third in $11 \cdot 9$ ways.

Summing over $0, 1, 2,$ or $3$ substitutions, $n = 1 + 11 \cdot 11 + 11^2 \cdot 11 \cdot 10 + 11^3 \cdot 11 \cdot 10 \cdot 9 = 1 + 121 + 13310 + 1317690 = 1331122.$ The remainder upon division by $1000$ is $122.$

2019 AIME I Problem 4

Solution:

Problem 4 in Other Years