Form a dollar from n coins

[bonanova]

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?

[markdane22]

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 January 23, 2013 by markdane22

[bonanova]

Hi markdane, and welcome to the Den.

That's the answer. Thanks for posting.