A cricket can jump two distances: 9 and 8 meters. It competes in a 100-meter race to the edge of a cliff. How many jumps must the cricket make to reach the end of the race without going past the finish line and falling off the cliff?

#
Solution

First solution: Suppose the cricket only jumps 9 meters. On its twelfth jump, it would fall off the cliff, since $9 \cdot 12 = 108 \, \text{m}$. Since it can also jump 8 meters, it is enough to "exchange" 8 jumps of 9 meters for jumps of 8 meters. Thus, we have 4 jumps of 9 meters and 8 jumps of 8 meters, for a total of $4 + 8 = 12$ jumps.

This is the only combination of jumps possible, because if the cricket makes fewer than 4 jumps of 9 meters, the maximum distances it can travel without falling off the cliff are: $3 \cdot 9 + 9 \cdot 8 = 99 \, \text{m}, 2 \cdot 9 + 10 \cdot 8 = 98 \, \text{m}, 1 \cdot 9 + 11 \cdot 8 = 97 \, \text{m}, \text{and} 0 \cdot 9 + 12 \cdot 8 = 96 \, \text{m}$. Furthermore, if the cricket makes more than 4 jumps of 9 meters, it must make fewer than 8 jumps of 8 meters, and thus the maximum distances it can travel without falling off the cliff are: $5 \cdot 9 + 6 \cdot 8 = 93 \, \text{m}, 6 \cdot 9 + 5 \cdot 8 = 94 \, \text{m}, 7 \cdot 9 + 4 \cdot 8 = 95 \, \text{m}, 8 \cdot 9 + 3 \cdot 8 = 96 \, \text{m}, 9 \cdot 9 + 2 \cdot 8 = 97 \, \text{m}, 10 \cdot 9 + 1 \cdot 8 = 98 \, \text{m}, \text{and} 11 \cdot 9 + 0 \cdot 8 = 99 \, \text{m}$. Since none of these distances equal 100, there is no other combination.

Second solution: Let $x$ be the number of 9-meter jumps and $y$ be the number of 8-meter jumps. We want to determine $x + y$, knowing that:

$$
\begin{aligned}
100 & = 9x + 8y \\
& = 8(x + y) + x
\end{aligned}
$$

Since 100 leaves a remainder of 4 when divided by 8, the same must be true for the number $8(x + y) + x$. That is, $x$ must leave a remainder of 4 when divided by 8, since $8(x + y)$ is already a multiple of 8. If $x > 4$, we know that $x$ is at least $8 \cdot 1 + 4 = 12$, which is the next number that leaves a remainder of 4 when divided by 8 after 4. If the cricket makes 12 jumps of $9 \, \text{m}$, it will reach $9 \cdot 12 = 108 \, \text{m}$ and fall off the cliff. Therefore, $x = 4$, and after substituting $x$ into the equation above, we can conclude that $y = (100 - 9 \cdot 4) / 8 = 8$. Thus, the cricket must make $4 + 8 = 12$ jumps.