[bonanova]

A while ago for a minimal set of coin denominations that would

create any value less than a dollar with at most two coins

- i.e. change we could believe in.

Today we're asking about change from a slightly different perspective,

keeping the coin denominations of dollar, half-dollar, quarter, dime, nickel and penny.

For our international solvers these have respective values of $1.00, $0.50, $0.25, $0.10, $0.05, and $0.01.

Using as many of each of these coins as may be needed, how many different sets of coins are worth exactly one dollar?

Examples:

1. 1 dollar coin - one could represent as: [1 0 0 0 0 0]
2. 1 half-dollar, 1 quarter, 1 dime, 2 nickels, 5 pennies - [0 1 1 1 2 5]
3. 100 pennies - [0 0 0 0 0 100]

etc.

For those who distinguish combinations and permutations, we're talking about combinations.

[Guest]

293

[Guest]

I just started with the pennies

21 possible choices for the amount of pennies

[0,100] where the # of pennies is divisible by 5 as no other coin is divisible by less than 5

This directly mirrors the nickels as the two are interchangeable. choose one nickel or five pennies

adding dimes

choosing zero results in the same solutions above

choosing one results in 90 cents to be divided among [0, 18] nickels and [0, 90] pennies

two results in #N=[0,16] #P=[0, 80]...

#Dimes = 0 1 2 3 4 5 6 7 8 9 10

#Combinations of N and P = 21 19 17 15 13 11 9 7 5 3 1

121 total

Repeat

for 121+121=242

Repeat

for 242+49=291

for 291+1=292

for 292+1=293

293 possible solutions

I'm sure there's a better way to do this

[Guest]

[1,0,0,0,0,0]

[0,2,0,0,0,0]

[0,1,2,0,0,0]

[0,1,1,2,1,0]

[0,1,1,2,0,5]

[0,1,1,1,3,0]

[0,1,1,1,2,5]

[0,1,1,1,1,10]

[0,1,1,1,0,15]

[0,1,1,0,5,0]

[0,1,1,0,4,5]

[0,1,1,0,3,10]

[0,1,1,0,2,15]

[0,1,1,0,1,20]

[0,1,1,0,0,25]

[0,1,0,5,0,0]

[0,1,0,4,2,0]

[0,1,0,4,1,5]

[0,1,0,4,0,10]

[0,1,0,3,4,0]

[0,1,0,3,3,5]

[0,1,0,3,2,10]

[0,1,0,3,1,15]

[0,1,0,3,0,20]

[0,1,0,2,6,0]

[0,1,0,2,5,5]

[0,1,0,2,4,10]

[0,1,0,2,3,15]

[0,1,0,2,2,20]

[0,1,0,2,1,25]

[0,1,0,2,0,30]

[0,1,0,1,8,0]

[0,1,0,1,7,5]

[0,1,0,1,6,10]

[0,1,0,1,5,15]

[0,1,0,1,4,20]

[0,1,0,1,3,25]

[0,1,0,1,2,30]

[0,1,0,1,1,35]

[0,1,0,1,0,40]

[0,1,0,0,9,5]

[0,1,0,0,8,10]

[0,1,0,0,7,15]

[0,1,0,0,6,20]

[0,1,0,0,5,25]

[0,1,0,0,4,30]

[0,1,0,0,3,35]

[0,1,0,0,2,40]

[0,1,0,0,10,0]

[0,1,0,0,1,45]

[0,1,0,0,0,50]

[0,0,4,0,0,0]

[0,0,3,2,1,0]

[0,0,3,2,0,5]

[0,0,3,1,3,0]

[0,0,3,1,2,5]

[0,0,3,1,1,10]

[0,0,3,1,0,15]

[0,0,3,0,5,0]

[0,0,3,0,4,5]

[0,0,3,0,3,10]

[0,0,3,0,2,15]

[0,0,3,0,1,20]

[0,0,3,0,0,25]

[0,0,2,5,0,0]

[0,0,2,4,2,0]

[0,0,2,4,1,5]

[0,0,2,4,0,10]

[0,0,2,3,4,0]

[0,0,2,3,3,5]

[0,0,2,3,2,10]

[0,0,2,3,1,15]

[0,0,2,3,0,20]

[0,0,2,2,6,0]

[0,0,2,2,5,5]

[0,0,2,2,4,10]

[0,0,2,2,3,15]

[0,0,2,2,2,20]

[0,0,2,2,1,25]

[0,0,2,2,0,30]

[0,0,2,1,8,0]

[0,0,2,1,7,5]

[0,0,2,1,6,10]

[0,0,2,1,5,15]

[0,0,2,1,4,20]

[0,0,2,1,3,25]

[0,0,2,1,2,30]

[0,0,2,1,1,35]

[0,0,2,1,0,40]

[0,0,2,0,9,5]

[0,0,2,0,8,10]

[0,0,2,0,7,15]

[0,0,2,0,6,20]

[0,0,2,0,5,25]

[0,0,2,0,4,30]

[0,0,2,0,3,35]

[0,0,2,0,2,40]

[0,0,2,0,10,0]

[0,0,2,0,1,45]

[0,0,2,0,0,50]

[0,0,1,7,1,0]

[0,0,1,7,0,5]

[0,0,1,6,3,0]

[0,0,1,6,2,5]

[0,0,1,6,1,10]

[0,0,1,6,0,15]

[0,0,1,5,5,0]

[0,0,1,5,4,5]

[0,0,1,5,3,10]

[0,0,1,5,2,15]

[0,0,1,5,1,20]

[0,0,1,5,0,25]

[0,0,1,4,7,0]

[0,0,1,4,6,5]

[0,0,1,4,5,10]

[0,0,1,4,4,15]

[0,0,1,4,3,20]

[0,0,1,4,2,25]

[0,0,1,4,1,30]

[0,0,1,4,0,35]

[0,0,1,3,9,0]

[0,0,1,3,8,5]

[0,0,1,3,7,10]

[0,0,1,3,6,15]

[0,0,1,3,5,20]

[0,0,1,3,4,25]

[0,0,1,3,3,30]

[0,0,1,3,2,35]

[0,0,1,3,1,40]

[0,0,1,3,0,45]

[0,0,1,2,9,10]

[0,0,1,2,8,15]

[0,0,1,2,7,20]

[0,0,1,2,6,25]

[0,0,1,2,5,30]

[0,0,1,2,4,35]

[0,0,1,2,3,40]

[0,0,1,2,2,45]

[0,0,1,2,11,0]

[0,0,1,2,10,5]

[0,0,1,2,1,50]

[0,0,1,2,0,55]

[0,0,1,1,9,20]

[0,0,1,1,8,25]

[0,0,1,1,7,30]

[0,0,1,1,6,35]

[0,0,1,1,5,40]

[0,0,1,1,4,45]

[0,0,1,1,3,50]

[0,0,1,1,2,55]

[0,0,1,1,13,0]

[0,0,1,1,12,5]

[0,0,1,1,11,10]

[0,0,1,1,10,15]

[0,0,1,1,1,60]

[0,0,1,1,0,65]

[0,0,1,0,9,30]

[0,0,1,0,8,35]

[0,0,1,0,7,40]

[0,0,1,0,6,45]

[0,0,1,0,5,50]

[0,0,1,0,4,55]

[0,0,1,0,3,60]

[0,0,1,0,2,65]

[0,0,1,0,15,0]

[0,0,1,0,14,5]

[0,0,1,0,13,10]

[0,0,1,0,12,15]

[0,0,1,0,11,20]

[0,0,1,0,10,25]

[0,0,1,0,1,70]

[0,0,1,0,0,75]

[0,0,0,9,2,0]

[0,0,0,9,1,5]

[0,0,0,9,0,10]

[0,0,0,8,4,0]

[0,0,0,8,3,5]

[0,0,0,8,2,10]

[0,0,0,8,1,15]

[0,0,0,8,0,20]

[0,0,0,7,6,0]

[0,0,0,7,5,5]

[0,0,0,7,4,10]

[0,0,0,7,3,15]

[0,0,0,7,2,20]

[0,0,0,7,1,25]

[0,0,0,7,0,30]

[0,0,0,6,8,0]

[0,0,0,6,7,5]

[0,0,0,6,6,10]

[0,0,0,6,5,15]

[0,0,0,6,4,20]

[0,0,0,6,3,25]

[0,0,0,6,2,30]

[0,0,0,6,1,35]

[0,0,0,6,0,40]

[0,0,0,5,9,5]

[0,0,0,5,8,10]

[0,0,0,5,7,15]

[0,0,0,5,6,20]

[0,0,0,5,5,25]

[0,0,0,5,4,30]

[0,0,0,5,3,35]

[0,0,0,5,2,40]

[0,0,0,5,10,0]

[0,0,0,5,1,45]

[0,0,0,5,0,50]

[0,0,0,4,9,15]

[0,0,0,4,8,20]

[0,0,0,4,7,25]

[0,0,0,4,6,30]

[0,0,0,4,5,35]

[0,0,0,4,4,40]

[0,0,0,4,3,45]

[0,0,0,4,2,50]

[0,0,0,4,12,0]

[0,0,0,4,11,5]

[0,0,0,4,10,10]

[0,0,0,4,1,55]

[0,0,0,4,0,60]

[0,0,0,3,9,25]

[0,0,0,3,8,30]

[0,0,0,3,7,35]

[0,0,0,3,6,40]

[0,0,0,3,5,45]

[0,0,0,3,4,50]

[0,0,0,3,3,55]

[0,0,0,3,2,60]

[0,0,0,3,14,0]

[0,0,0,3,13,5]

[0,0,0,3,12,10]

[0,0,0,3,11,15]

[0,0,0,3,10,20]

[0,0,0,3,1,65]

[0,0,0,3,0,70]

[0,0,0,2,9,35]

[0,0,0,2,8,40]

[0,0,0,2,7,45]

[0,0,0,2,6,50]

[0,0,0,2,5,55]

[0,0,0,2,4,60]

[0,0,0,2,3,65]

[0,0,0,2,2,70]

[0,0,0,2,16,0]

[0,0,0,2,15,5]

[0,0,0,2,14,10]

[0,0,0,2,13,15]

[0,0,0,2,12,20]

[0,0,0,2,11,25]

[0,0,0,2,10,30]

[0,0,0,2,1,75]

[0,0,0,2,0,80]

[0,0,0,10,0,0]

[0,0,0,1,9,45]

[0,0,0,1,8,50]

[0,0,0,1,7,55]

[0,0,0,1,6,60]

[0,0,0,1,5,65]

[0,0,0,1,4,70]

[0,0,0,1,3,75]

[0,0,0,1,2,80]

[0,0,0,1,18,0]

[0,0,0,1,17,5]

[0,0,0,1,16,10]

[0,0,0,1,15,15]

[0,0,0,1,14,20]

[0,0,0,1,13,25]

[0,0,0,1,12,30]

[0,0,0,1,11,35]

[0,0,0,1,10,40]

[0,0,0,1,1,85]

[0,0,0,1,0,90]

[0,0,0,0,9,55]

[0,0,0,0,8,60]

[0,0,0,0,7,65]

[0,0,0,0,6,70]

[0,0,0,0,5,75]

[0,0,0,0,4,80]

[0,0,0,0,3,85]

[0,0,0,0,20,0]

[0,0,0,0,2,90]

[0,0,0,0,19,5]

[0,0,0,0,18,10]

[0,0,0,0,17,15]

[0,0,0,0,16,20]

[0,0,0,0,15,25]

[0,0,0,0,14,30]

[0,0,0,0,13,35]

[0,0,0,0,12,40]

[0,0,0,0,11,45]

[0,0,0,0,10,50]

[0,0,0,0,1,95]

[0,0,0,0,0,100]

Count: 293 as everyone else said.