Jump to content
BrainDen.com - Brain Teasers
  • 0

Form a dollar from n coins


bonanova
 Share

Question

You are given n > 0 of each of the standard denomination US coins: 1¢, 5¢, 10¢, 25¢, 50¢, $1.

Your task is then to select from them a set of n coins whose total value is exactly $1.

Clearly, if n=1, you can do this by selecting the $1 coin. If n=2 you select the two half-dollar coins.

But if n > 100, then every set of n coins (e.g. all the pennies) will have a total that is too large.

What is the smallest n such that it is impossible to select n coins that make exactly a dollar?

Link to comment
Share on other sites

2 answers to this question

Recommended Posts

  • 0

As this question was getting no answers, I have cheated and made the program ^_^ :

------------So I think 77 is the answer -------

Number of coins: 1 => 1$*1 + 50c*0 + 25c*0 + 10c*0 + 5c*0 + 1c*0
Number of coins: 2 => 1$*0 + 50c*2 + 25c*0 + 10c*0 + 5c*0 + 1c*0
Number of coins: 3 => 1$*0 + 50c*1 + 25c*2 + 10c*0 + 5c*0 + 1c*0
Number of coins: 4 => 1$*0 + 50c*0 + 25c*4 + 10c*0 + 5c*0 + 1c*0
Number of coins: 5 => 1$*0 + 50c*1 + 25c*1 + 10c*2 + 5c*1 + 1c*0
Number of coins: 6 => 1$*0 + 50c*1 + 25c*1 + 10c*1 + 5c*3 + 1c*0
Number of coins: 7 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*5 + 1c*0
Number of coins: 8 => 1$*0 + 50c*1 + 25c*0 + 10c*3 + 5c*4 + 1c*0
Number of coins: 9 => 1$*0 + 50c*1 + 25c*1 + 10c*2 + 5c*0 + 1c*5
Number of coins: 10 => 1$*0 + 50c*1 + 25c*1 + 10c*1 + 5c*2 + 1c*5
Number of coins: 11 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*4 + 1c*5
Number of coins: 12 => 1$*0 + 50c*1 + 25c*0 + 10c*3 + 5c*3 + 1c*5
Number of coins: 13 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*5 + 1c*5
Number of coins: 14 => 1$*0 + 50c*1 + 25c*1 + 10c*1 + 5c*1 + 1c*10
Number of coins: 15 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*3 + 1c*10
Number of coins: 16 => 1$*0 + 50c*1 + 25c*0 + 10c*3 + 5c*2 + 1c*10
Number of coins: 17 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*4 + 1c*10
Number of coins: 18 => 1$*0 + 50c*1 + 25c*1 + 10c*1 + 5c*0 + 1c*15
Number of coins: 19 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*2 + 1c*15
Number of coins: 20 => 1$*0 + 50c*1 + 25c*0 + 10c*3 + 5c*1 + 1c*15
Number of coins: 21 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*3 + 1c*15
Number of coins: 22 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*5 + 1c*15
Number of coins: 23 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*1 + 1c*20
Number of coins: 24 => 1$*0 + 50c*1 + 25c*0 + 10c*3 + 5c*0 + 1c*20
Number of coins: 25 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*2 + 1c*20
Number of coins: 26 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*4 + 1c*20
Number of coins: 27 => 1$*0 + 50c*1 + 25c*1 + 10c*0 + 5c*0 + 1c*25
Number of coins: 28 => 1$*0 + 50c*0 + 25c*3 + 10c*0 + 5c*0 + 1c*25
Number of coins: 29 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*1 + 1c*25
Number of coins: 30 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*3 + 1c*25
Number of coins: 31 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*5 + 1c*25
Number of coins: 32 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*5 + 1c*25
Number of coins: 33 => 1$*0 + 50c*1 + 25c*0 + 10c*2 + 5c*0 + 1c*30
Number of coins: 34 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*2 + 1c*30
Number of coins: 35 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*4 + 1c*30
Number of coins: 36 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*4 + 1c*30
Number of coins: 37 => 1$*0 + 50c*0 + 25c*1 + 10c*3 + 5c*3 + 1c*30
Number of coins: 38 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*1 + 1c*35
Number of coins: 39 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*3 + 1c*35
Number of coins: 40 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*3 + 1c*35
Number of coins: 41 => 1$*0 + 50c*0 + 25c*1 + 10c*3 + 5c*2 + 1c*35
Number of coins: 42 => 1$*0 + 50c*1 + 25c*0 + 10c*1 + 5c*0 + 1c*40
Number of coins: 43 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*2 + 1c*40
Number of coins: 44 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*2 + 1c*40
Number of coins: 45 => 1$*0 + 50c*0 + 25c*1 + 10c*3 + 5c*1 + 1c*40
Number of coins: 46 => 1$*0 + 50c*0 + 25c*1 + 10c*2 + 5c*3 + 1c*40
Number of coins: 47 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*1 + 1c*45
Number of coins: 48 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*1 + 1c*45
Number of coins: 49 => 1$*0 + 50c*0 + 25c*1 + 10c*3 + 5c*0 + 1c*45
Number of coins: 50 => 1$*0 + 50c*0 + 25c*1 + 10c*2 + 5c*2 + 1c*45
Number of coins: 51 => 1$*0 + 50c*1 + 25c*0 + 10c*0 + 5c*0 + 1c*50
Number of coins: 52 => 1$*0 + 50c*0 + 25c*2 + 10c*0 + 5c*0 + 1c*50
Number of coins: 53 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*5 + 1c*45
Number of coins: 54 => 1$*0 + 50c*0 + 25c*1 + 10c*2 + 5c*1 + 1c*50
Number of coins: 55 => 1$*0 + 50c*0 + 25c*1 + 10c*1 + 5c*3 + 1c*50
Number of coins: 56 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*5 + 1c*50
Number of coins: 57 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*4 + 1c*50
Number of coins: 58 => 1$*0 + 50c*0 + 25c*1 + 10c*2 + 5c*0 + 1c*55
Number of coins: 59 => 1$*0 + 50c*0 + 25c*1 + 10c*1 + 5c*2 + 1c*55
Number of coins: 60 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*4 + 1c*55
Number of coins: 61 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*3 + 1c*55
Number of coins: 62 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*5 + 1c*55
Number of coins: 63 => 1$*0 + 50c*0 + 25c*1 + 10c*1 + 5c*1 + 1c*60
Number of coins: 64 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*3 + 1c*60
Number of coins: 65 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*2 + 1c*60
Number of coins: 66 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*4 + 1c*60
Number of coins: 67 => 1$*0 + 50c*0 + 25c*1 + 10c*1 + 5c*0 + 1c*65
Number of coins: 68 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*2 + 1c*65
Number of coins: 69 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*1 + 1c*65
Number of coins: 70 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*3 + 1c*65
Number of coins: 71 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*5 + 1c*65
Number of coins: 72 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*1 + 1c*70
Number of coins: 73 => 1$*0 + 50c*0 + 25c*0 + 10c*3 + 5c*0 + 1c*70
Number of coins: 74 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*2 + 1c*70
Number of coins: 75 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*4 + 1c*70
Number of coins: 76 => 1$*0 + 50c*0 + 25c*1 + 10c*0 + 5c*0 + 1c*75
Number of coins: 77 => can't find any solution
Number of coins: 78 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*1 + 1c*75
Number of coins: 79 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*3 + 1c*75
Number of coins: 80 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*5 + 1c*75
Number of coins: 81 => can't find any solution
Number of coins: 82 => 1$*0 + 50c*0 + 25c*0 + 10c*2 + 5c*0 + 1c*80
Number of coins: 83 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*2 + 1c*80
Number of coins: 84 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*4 + 1c*80
Number of coins: 85 => can't find any solution
Number of coins: 86 => can't find any solution
Number of coins: 87 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*1 + 1c*85
Number of coins: 88 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*3 + 1c*85
Number of coins: 89 => can't find any solution
Number of coins: 90 => can't find any solution
Number of coins: 91 => 1$*0 + 50c*0 + 25c*0 + 10c*1 + 5c*0 + 1c*90
Number of coins: 92 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*2 + 1c*90
Number of coins: 93 => can't find any solution
Number of coins: 94 => can't find any solution
Number of coins: 95 => can't find any solution
Number of coins: 96 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*1 + 1c*95
Number of coins: 97 => can't find any solution
Number of coins: 98 => can't find any solution
Number of coins: 99 => can't find any solution
Number of coins: 100 => 1$*0 + 50c*0 + 25c*0 + 10c*0 + 5c*0 + 1c*100

Edited by markdane22
Link to comment
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...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...