Jump to content
BrainDen.com - Brain Teasers

Question

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.

Link to post
Share on other sites

3 answers to this question

Recommended Posts

  • 0

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

Link to post
Share on other sites
  • 0

[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.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...