Question

How many different ways can you make 82 cents using current u.s. currency

Answer 1

 You can probably just work it out. 

You need non-negative integer solutions to p+5n+10d+25q = 82. 

If p = leftovers, then you simply need 5n + 10d + 25q ≤ 80. 


So this is the same as n + 2d + 5q ≤ 16 

So now you simply have to "crank out" the cases. 

Case q=0 [ n + 2d ≤ 16 ] 

Case (q=0,d=0) → n = 0 through 16 [17 possibilities] 
Case (q=0,d=1) → n = 0 through 14 [15 possibilities] 
... 
Case (q=0,d=7) → n = 0 through 2 [3 possibilities] 
Case (q=0,d=8) → n = 0 [1 possibility] 

Total from q=0 case: 1 + 3 + ... + 15 + 17 = 81 

Case q=1 [ n + 2d ≤ 11 ] 
Case (q=1,d=0) → n = 0 through 11 [12] 
Case (q=1,d=1) → n = 0 through 9 [10] 
... 
Case (q=1,d=5) → n = 0 through 1 [2] 

Total from q=1 case: 2 + 4 + ... + 10 + 12 = 42 

Case q=2 [ n + 2 ≤ 6 ] 
Case (q=2,d=0) → n = 0 through 6 [7] 
Case (q=2,d=1) → n = 0 through 4 [5] 
Case (q=2,d=2) → n = 0 through 2 [3] 
Case (q=2,d=3) → n = 0 [1] 

Total from case q=2: 1 + 3 + 5 + 7 = 16 

Case q=3 [ n + 2d ≤ 1 ] 
Here d must be 0, so there is only the case: 
Case (q=3,d=0) → n = 0 through 1 [2] 

So the case q=3 only has 2. 

Grand total: 2 + 16 + 42 + 81 = 141