2000 AMC 10 Problem 17

P16-20~3 minPrint

Modular Arithmetic Games & Processes Use an invariant, parity, or coloring argument

Boris has an incredible coin-changing machine. When he puts in a quarter, it returns five nickels; when he puts in a nickel, it returns five pennies; and when he puts in a penny, it returns five quarters. Boris starts with just one penny. Which of the following amounts could Boris have after using the machine repeatedly?

Show solution without answering

Key insight

Trading a quarter or a nickel keeps the money the same. Trading a penny adds exactly 124 cents. So any total is 1 cent more than a multiple of 124.

Solution

1. Watch what each trade does to the total amount of money, in cents.
- A quarter ( $25$ cents) becomes five nickels ( $25$ cents). No change.
- A nickel ( $5$ cents) becomes five pennies ( $5$ cents). No change.
- A penny ( $1$ cent) becomes five quarters ( $125$ cents). A gain of $124$ cents.
2. Boris starts with $1$ cent. Only the penny trade changes the total, and each time it adds $124$ . So his total is always
$1,\ 1 + 124,\ 1 + 2 \cdot 124,\ \ldots$
that is, $1$ more than a multiple of $124$ .
3. Subtract $1$ from each choice and see which result divides evenly by $124$ :

choice	minus 1	divided by 124
$363$	$362$	$2$ remainder $114$
$513$	$512$	$4$ remainder $16$
$630$	$629$	$5$ remainder $9$
$745$	$744$	exactly $6$
$907$	$906$	$7$ remainder $38$

Only $\$7.45$ works. It really can happen: he always has a penny available (break a quarter into nickels and a nickel into pennies if needed), so he can do the penny trade $6$ times.

The answer is $\boxed{\textbf{(D)}\ \$7.45}$ .

Why this works

When a process has only a few kinds of moves, ask what each move does to one simple number, here the total in cents. Two moves leave it alone and one adds a fixed $124$ , so the total is always "start plus some number of 124s." That one fact rules out four choices without acting out a single trade.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Track the total value in cents through each kind of exchange.

Quarter in, five nickels out: $25 \to 25$ , no change.
Nickel in, five pennies out: $5 \to 5$ , no change.
Penny in, five quarters out: $1 \to 125$ , a gain of $124$ .

So no matter what Boris does, his total is $1 + 124k$ cents, where $k$ counts how many pennies he has fed in. Subtract $1$ from each choice and test divisibility by $124$ :
$362 = 2 \cdot 124 + 114,\quad 512 = 4 \cdot 124 + 16,\quad 629 = 5 \cdot 124 + 9,\quad 744 = 6 \cdot 124,\quad 906 = 7 \cdot 124 + 38.$
Only $\$7.45$ fits, with $k = 6$ . (It is also reachable: each time, break a quarter into nickels and a nickel into pennies, then feed in a penny.)

The answer is $\boxed{\textbf{(D)}\ \$7.45}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic
Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Introduction to Number Theory, Chapter 10: Units Digits
Introduction to Number Theory, Chapter 14: Linear Congruences (§14.4)