Can someone help me solve this word problem using a diophantine equation?

A man has $4.55 in change composed entirely of dimes and quarters. What are the maximum and minimum number of coins that he can have? Is it possible for the number of dimes to equal the number of quarters.

So far I set up what was given so I have: x= # of dimes y= # of quarters 455=total 10=cost of dime 25=cost of quarter

equation: 10x+25y=455 so I found the gcd(25,10)=5 and since gcd(25,10)|455 there is a solution.

where do I go from here?

  • $\begingroup$ I'm still trying to figure out if this problem is about quarters or nickels. Both sets of numbers and names make appearances here... $\endgroup$ – Eric Towers Mar 2 '14 at 23:55
  • $\begingroup$ sorry I made an error; I corrected the problem it is quarters and dimes $\endgroup$ – Lil Mar 2 '14 at 23:56
  • $\begingroup$ From a specific solution, ask yourself what the tradeoff between whatever two coins you have is. 5 dimes = 2 quarters. Alternatively, 5 nickels = 1 quarter. This should let you exchange some of one kind of coin for the other so you can walk through the set of possible solutions. $\endgroup$ – Eric Towers Mar 2 '14 at 23:56
  • $\begingroup$ my bad, that was from before too $\endgroup$ – Lil Mar 2 '14 at 23:58

For the first question.

You can write the equation as $$10x+25y=455$$ or equivalently as $$2x+5y=91$$ So you can see that the maximal admissible value for $y$ is one such that $5y=85$ which gives $y=17$. Then $x=3$. Accordingly, the maximum value for $x$ is one such that $2x=86$ which gives $x=43$ and $y=1$. In the first case you have the minimum number of coins $(20)$ (since it corresponds to the maximum possible value of quarters - the higher valued coin) and in the second the maximum $(44)$ (since it corresponds to the maximum possible value of dimes - the lower valued coin).

For the second question. Just set $x=y$ and see if you can solve the equation (which you can for $x=y=13$).

  • $\begingroup$ sorry, can you help me through the problem using the values I just got.. I used the Euclidean Algorithm and found x=91 and y=-364 for one solution. Now to find all solutions I was going to plug it into the formula: x+b/dt and the same for y is that correct? $\endgroup$ – Lil Mar 3 '14 at 0:08
  • $\begingroup$ the problem is when I plugged x and y into the formula I got x'=86t and y'=-362t then to find the solution I was going to set both values to greater than 0 but that didn't work out.. $\endgroup$ – Lil Mar 3 '14 at 0:09
  • $\begingroup$ but you cannot have y<0. and you do not need all the solutions, you need only maximum and minimum number of coins $\endgroup$ – Jimmy R. Mar 3 '14 at 0:10
  • $\begingroup$ ok, so was it incorrect for me to find one solution being x=91 and y=-364 or is that step fine? $\endgroup$ – Lil Mar 3 '14 at 0:11
  • $\begingroup$ no, is not fine, you cannot have -364dimes! the euclidean algorith cannot help you to find the solutions faster than the intuitive approach that maximum is attained when you have maximum dimes and minimum is attained when you have maximum quarters $\endgroup$ – Jimmy R. Mar 3 '14 at 0:12

x = number of dimes, and y = number of quarters. Then: .1x + .25y = 4.55 ==> 10x + 25y = 455 ==> 2x + 5y = 91 ==> 5y < 91 ==> y <= 18. So you have: (x,y) = (43,1),(38,3),(33,5),(28,7),(23,9),(18,11),(13,13),(8,15),(3,17).


If you have a combination that has two or more quarters, you can swap out a pair of quarters for five dimes, so if you want to maximize the total number of coins, you don't want more than one quarter. You can't make \$4.55 with dimes alone, but you can make \$4.30 with 43 dimes, so the maximum number of coins is 44.

Likewise, to minimize the total number of coins, you want to use as many quarters as possible and as few dimes, so subtract 10's from 455 until you get a multiple of 25, which happens at $455-30=425$, that is, $3$ dimes and $17$ quarters, for a total of $20$ coins.

Finally, you can make a combination with equal numbers of dimes and quarters if and only if $10+25=35$ divides $455$, which it does: $455=35\times13$.

One quibble: If $\gcd(a,b)|c$, then it's true that the equation $ax+by=c$ has integer solutions, but there still may not be any solutions in nonnegative integers, which this problem tacitly calls for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.