From: karr@cs.cornell.edu (David Karr) Subject: Re: More coin arithmetic Date: Wed, 10 Mar 1993 01:44:46 GMT In article <1993Mar9.234016.917@news.eng.convex.com> dodson@convex.COM (Dave Dodson) writes: >Call a number n > 0 a "dollar number" if there is a way to make exactly one >US dollar with exactly "n" US coins (denominations $.01, $.05, $.10, $.25, >$.50, and $1.00). What is the smallest n > 0 that is not a dollar number? n = 77. For n = 1 to 4 there are obvious combinations of 1.00, .50, and .25. For n = 5 and 6, use 1.00 = .50 + .25 + .10 + .10 + .05, then .50 = 2*.25. For n = 7 to 9, use 1.00 = 2*.25 + 5*.10, then apply .10 = 2*.05 twice. For n = 10 to 19, use 1.00 = 10*.10 and apply .10 = 2*.05 nine times. For n = 20 to 76, vary the breakdown of the first 30 cents from 3 to 6 coins using .30 = 3*.10 = 2*.10 + 2*.05 = .10 + 4*.05 = 6*.05; the remaining 70 cents starts out as nickels which you convert to pennies one at a time, raising the count by 4 each time. Thus you get from 20 nickels to 70 pennies and 6 nickels. To get 77 coins, suppose these include 5k pennies (must have a multiple of 5 because every other coin is congruent to 0 mod 5 cents). Then the remaining 100 - 5k cents must consist of 77 - 5k coins. Since each remaining coin is worth at least 5 cents, the non-penny value in cents is at least 5 times the non-penny coin count: 100 - 5k >= 5 * (77 - 5k) By algebra: 20 - k >= 77 - 5k 4k >= 57 k >= 57/4 = 14.25 Since k is an integer, k >= 15, i.e. we must have at least 5*15 = 75 pennies. We can't have more because 5*16 = 80 is already greater than 77. But then we must find exactly two coins to add up to the remaining 25 cents. By exhaustive search we show there is no such combination. We can't make 1.00 in 77 coins. -- David Karr (karr@cs.cornell.edu) *** From: positron@quip.eecs.umich.edu (Jonathan Haas) dodson@convex.COM (Dave Dodson) writes: >Call a number n > 0 a "dollar number" if there is a way to make exactly one >US dollar with exactly "n" US coins (denominations $.01, $.05, $.10, $.25, >$.50, and $1.00). What is the smallest n > 0 that is not a dollar number? Spoiler... I solved this one through the time-honored technique of "brute force". The answer is 77. Let P be a penny, N be a nickel, D be a dime, Q be a quarter, H be a half dollar, and F be a dollar coin. 1: F 2: HH 3: HQQ 4: QQQQ 5: HQDDN 6: QQQDDN 7: QQDDDDD 8: QQDDDDNN 9: QQDDDNNNN 10: QQDDNNNNNN 11: QQDNNNNNNNN 12: QQNNNNNNNNNN 13: QDDDNNNNNNNNN 14: QDDNNNNNNNNNNN 15: QDNNNNNNNNNNNNN 16: QNNNNNNNNNNNNNNN 17: DDDNNNNNNNNNNNNNN 18: DDNNNNNNNNNNNNNNNN 19: DNNNNNNNNNNNNNNNNNN 20: NNNNNNNNNNNNNNNNNNNN 21: DDDNNNNNNNNNNNNNPPPPP 22: DDNNNNNNNNNNNNNNNPPPPP 23: DNNNNNNNNNNNNNNNNNPPPPP 24: NNNNNNNNNNNNNNNNNNNPPPPP 25: DDDNNNNNNNNNNNNPPPPPPPPPP 26: DDNNNNNNNNNNNNNNPPPPPPPPPP 27: DNNNNNNNNNNNNNNNNPPPPPPPPPP 28: NNNNNNNNNNNNNNNNNNPPPPPPPPPP 29: DDDNNNNNNNNNNNPPPPPPPPPPPPPPP 30: DDNNNNNNNNNNNNNPPPPPPPPPPPPPPP 31: DNNNNNNNNNNNNNNNPPPPPPPPPPPPPPP 32: NNNNNNNNNNNNNNNNNPPPPPPPPPPPPPPP 33: DDDNNNNNNNNNNPPPPPPPPPPPPPPPPPPPP 34: DDNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPP 35: DNNNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPP 36: NNNNNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPP 37: DDDNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPP 38: DDNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPP 39: DNNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPP 40: NNNNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPP 41: DDDNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 42: DDNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 43: DNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 44: NNNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 45: DDDNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 46: DDNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 47: DNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 48: NNNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 49: DDDNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 50: DDNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 51: DNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 52: NNNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 53: DDDNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 54: DDNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 55: DNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 56: NNNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 57: DDDNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 58: DDNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 59: DNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 60: NNNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 61: DDDNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 62: DDNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 63: DNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 64: NNNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 65: DDDNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 66: DDNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 67: DNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 68: NNNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 69: DDDNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 70: DDNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 71: DNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 72: NNNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 73: DDDPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 74: DDNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 75: DNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP 76: NNNNNNPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP There is no solution for 77. You can see this by realizing that, if there are 75 pennies, you must get 25 cents from two coins (impossible), or if there are 75 - 5X pennies, you must get 25 + 5X cents from 2 + 5X coins, also impossible. Going onward, and abbreviating 5 pennies as "5", we get: 78: DDN555555555555555 79: DNNN555555555555555 80: NNNNN555555555555555 81: No solution. In fact, there is no solution for any 77+4X. 82: DD5555555555555555 83: DNN5555555555555555 84: NNNN5555555555555555 85: No solution 86: No solution, or for any 86+4X 87: DN55555555555555555 88: NNN55555555555555555 89: No solution 90: No solution 91: D555555555555555555 92: NN555555555555555555 93: No solution 94: No solution 95: No solution, or for any 95+4X 96: N5555555555555555555 97: No solution 98: No solution 99: No solution 100: 55555555555555555555 No solution exists, of course, for any N>100. -- __/\__ Jonathan S. Haas | Jake liked his women the way he liked \ / University of Michigan | his kiwi fruit: sweet yet tart, firm- /_ _\ positron@eecs.umich.edu | fleshed yet yielding to the touch, and \/ PGP 2.1 key by request | covered with short brown fuzzy hair. *** From: boll@CS.ColoState.EDU (dave boll) In article <1993Mar10.021319.5775@zip.eecs.umich.edu> positron@quip.eecs.umich.edu (Jonathan Haas) writes: >dodson@convex.COM (Dave Dodson) writes: >>Call a number n > 0 a "dollar number" if there is a way to make exactly one >>US dollar with exactly "n" US coins (denominations $.01, $.05, $.10, $.25, >>$.50, and $1.00). What is the smallest n > 0 that is not a dollar number? > >I solved this one through the time-honored technique of "brute force". >The answer is 77. > Follow-up puzzle: which of the first 76 numbers is a dollar number in the most number of ways? ------------------------------------------------------------ Dave Boll boll@handel.cs.colostate.edu "The speed of time is 1 second per second" ------------------------------------------------------------