[Math] find the five different ways to combine 100 pennies, quarters, and dimes to get $\$4.99$

combinatoricselementary-number-theory

here's where I am so far.

I define two equations with three variables

  • $q$: the number of quarters,
  • $p$: the number of pennies, and
  • $d$: the number of dimes.

\begin{gather*}
p+d+q = 100\\\\
25q+10d+p = 499
\end{gather*}

I eliminate $q$ by substitution and get
$$
24p+15d = 2001
$$

now I'm lost. I think this has something to do with the $\gcd(24,15) = 3$.

however, I am unsure how to apply this information. I am certainly more interested in the process than just the solution. I'm having some trouble with how to solve a two variable equation.

Best Answer

Elimination is a good idea. I think the details are not done correctly. In any case, I would rather eliminate $p$, the arithmetic is easier. We get $24q+9d=399$, or equivalently $$8q+3d=133.$$

We can use general techniques to solve this Diophantine equation, but the numbers are so small that it does not seem worthwhile. Note that when $q=2$, then $133-8q$ is a multiple of $3$, and we get $q=2$, $d=39$, and therefore $p=59$.

Now we have found one solution. We need others.

Go back to the equation $8q+3d=133$. We have found one solution, $q=2$, $d=39$. For any integer $k$, we therefore have $$8(2+3k)+3(39-8k)=133.$$ (Note the cancellation.)

Substitute various values of $k$. With $k=1$, for example, we get the solution $q=5$, $d=31$. That gives $p=64$.

Continue, using $k=2$, $3$, and so on. For the sake of reality, we will have to make sure that our values of $q$, $d$, $p$ are all $\ge 0$. We cannot use $k\gt 4$, for that would give negative $d$.

Related Question