In the 1968 MAA High School Mathematics Contest (Problem #19), contestants encountered this classic Diophantine puzzle:

Let $n$ be the number of ways that 10 dollars can be changed into dimes and quarters, with at least one of each coin being used. Then $n$ equals:

$$\text{(A) } 40 \qquad \text{(B) } 38 \qquad \text{(C) } 21 \qquad \text{(D) } 20 \qquad \text{(E) } 19$$

Let $d$ denote the number of dimes ($10¢$) and $q$ denote the number of quarters ($25¢$). In cents, 10 dollars equals $1,000¢$: $$10d + 25q = 1000$$ Dividing the entire equation by $5$: $$2d + 5q = 200$$ We can solve for $2d$: $$2d = 200 - 5q = 5(40 - q)$$ Now consider the arithmetic constraints:

1. The problem specifies that at least one of each coin must be used, so $d \ge 1$ and $q \ge 1$.
2. Because $d \ge 1$, the left-hand side $2d$ is a positive even integer.
3. Therefore, the right-hand side $5(40 - q)$ must also be a positive even integer:
   • For $5(40 - q) > 0$, we must have $40 - q > 0 \implies q < 40$.
   • For $5(40 - q)$ to be even, $40 - q$ must be even, which means $q$ itself must be an even integer!
4. Since $q \ge 1$ and $q$ is even with $q < 40$, the allowable values for $q$ are: $$q \in \{2, 4, 6, 8, \dots, 36, 38\}$$

Writing $q = 2k$, we have $1 \le k \le 19$. There are exactly 19 possible values for $q$, each giving a unique positive integer $d = 100 - 5k$.

In this lesson, we write a program to search for all valid combinations of dimes and quarters, print the complete ledger of solutions, and verify the total count!

Move the mouse over a dotted box for more information.

The program finds that there are exactly 19 ways to make change for \$10 using at least one dime and at least one quarter. The solutions range from $2$ quarters and $95$ dimes to $38$ quarters and $5$ dimes.