Coin problem - all possible amounts from a set of coins

[musicgold]

Homework Statement

Given 8 dimes (10 ¢ coins) and 3 quarters (25 ¢ coins), how many different amounts
of money can be created using one or more of the 11 coins?

Relevant Equations

m = 10d + 25q , where 0 <= d < 9 and 0 <= q < 4
where d is number of dimes and q is number of quarters used to get a m.

While I found 26 possible values of m with the trial and error method, I wanted to find an elegant approach to solve such problems.

I think the following equation represents the problem:
m = 10d + 25q where ## 0 <= d < 9 ## and ## 0 <= q < 4 ##
where d is the number of dimes and q is number of quarters used to get a m.

As d can take 9 values and q can take 4 values, m can take 36 possible values, some of which will be duplicate. Note that the combination d=0, q= 0 is invalid.

I am not able to find a way to quickly isolate the potential duplicate values.
When d =5, m can have 4 values 50, 75, 100 and 125 cents. 50 and 75 will also be created with only 2 or 3 quarters. So I have found 2 duplicates, and 1 invalid amounts out of 10.

How should I move forward from here?

Thanks

 

[Frabjous]

I would look at the quarters. Their sums either end in 0 or 5.

 

[Hill]

If two combinations, ##d_1, q_1## and ##d_2, q_2## give the same ##m##, then
##10d_1+25q_1=10d_2+25q_2##
##10(d_1-d_2)=25(q_2-q_1)##.
I'd look at how many different solutions this equation has. ##q_2-q_1## has to be ##2##, etc.

 

[musicgold]

If two combinations, ##d_1, q_1## and ##d_2, q_2## give the same ##m##, then
##10d_1+25q_1=10d_2+25q_2##
##10(d_1-d_2)=25(q_2-q_1)##.
I'd look at how many different solutions this equation has. ##q_2-q_1## has to be ##2##, etc.

Got it. Thanks!
As shown below there are 8 duplicates.
I also realized that there are actually 27 unique values of m and not 26.

27 unique values + 8 duplicates + 1 invalid = 36 combinations

 

[phinds]

I think you left out the combination of no coins = zero cents so there are 28 unique and 8 dupes. Zero is a legitimate amount of money (I know 'cause my bank balance went there a couple of times in my younger days

 

[Frabjous]

I think you left out the combination of no coins = zero cents so there are 28 unique and 8 dupes. Zero is a legitimate amount of money (I know 'cause my bank balance went there a couple of times in my younger days

The homework statement says “using one or more of the 11 coins”.

 

[pasmith]

Two quarters are the same as 5 dimes. So points [itex](d,q)[/itex] which differ by integer multiples of [itex](5, -2)[/itex] give the same [itex]m[/itex].

 

[phinds]

The homework statement says “using one or more of the 11 coins”.

Ah HA ! I need to learn how to read.