What is the smallest number of coins that you can't make a dollar with?
combinatorics/coinage/impossible
Problem
What is the smallest number of coins that you can't make a dollar with? I.e., for what N does there not exist a set of N coins adding up to a dollar? It is possible to make a dollar with 1 current U.S. coin (a Susan B. Anthony), 2 coins (2 fifty cent pieces), 3 coins (2 quarters and a fifty cent piece), etc. It is not possible to make exactly a dollar with 101 coins.
Show solution
The answer is 77: a) 5c = 1 or 5; b) 10c = 1 or 2 a's (1,2,6,10) c) 25c = 1 or 2 b's + 1 a d) 50c = 1 or 2 c's e) $1 = 1 or 2 d's total penny nickel dime quarter half 5 1 2 1 1 6 3 1 1 1 7 5 1 1 8 4 3 1 9 6 2 1 10 8 1 1 11 10 1 12 7 4 1 13 9 3 1 14 11 2 1 15 13 1 1 16 15 1 17 14 3 18 16 2 19 18 1 20 20 21 5 13 3 22 5 15 2 23 5 17 1 24 5 19 25 10 12 3 26 10 14 2 27 10 16 1 28 10 18 29 15 11 3 30 15 13 2 31 15 15 1 32 15 17 33 20 10 3 34 20 12 2 35 20 14 1 36 20 16 37 25 9 3 38 25 11 2 39 25 13 1 40 25 15 41 30 8 3 42 30 10 2 43 30 12 1 44 30 14 45 35 7 3 46 35 9 2 47 35 11 1 48 35 13 49 40 6 3 50 40 8 2 51 40 10 1 52 40 12 53 45 5 3 54 45 7 2 55 45 9 1 56 45 11 57 50 4 3 58 50 6 2 59 50 8 1 60 50 10 61 55 3 3 62 55 5 2 63 55 7 1 64 55 9 65 60 2 3 66 60 4 2 67 60 6 1 68 60 8 69 65 1 3 70 65 3 2 71 65 5 1 72 65 7 73 70 3 74 70 2 2 75 70 4 1 76 70 6 77 can't be done 78 75 1 2 79 75 3 1 80 75 5 81 can't be done 82 80 2 83 80 2 1 84 80 4 85 can't be done 86 can't be done 87 85 1 1 88 85 3 89 can't be done 90 can't be done 91 90 1 92 90 2 93-95 can't be done 96 95 1 97-99 can't be done 100 100