Answer: Coins to make a dollar

The answer is 77, as follows:

For one coin, use a dollar coin; for 2, two half-dollars; for 3, a half-dollar and two quarters; for 4, four quarters; for 5, a half-dollar, a quarter, 2 dimes, and a nickel. This is the last we have to use the half-dollar.

For 6, use three quarters, two dimes, and a nickel. For 7 and 8, use the previous construction but break one or two dimes into two nickels. For 9, use a quarter, a nickel, and seven dimes. This is the last we have to use the quarter.

For 10, use ten dimes. For 11 through 20, progressively break dimes into two nickels until we have 20 nickels.

For 21, use three dimes, 13 nickels, and five pennies. For 22 through 24, break those three dimes into nickels.

For 25, use the 21 solution but break a nickel into five pennies. Similarly, the solutions for 26 through 28 are formed from the 22 through 24 solutions. Also similarly, the solutions for the next 48 numbers are formed by breaking the next 12 nickels. The last bunch, 73 through 76, have 70 pennies and some nickels and dimes adding to 30 cents.

77 is impossible. For proof, consider that at least 72 pennies must be used; if fewer than this are used, at least 6 coins are nickels or greater, and these plus the pennies add up to too much. However, pennies can only be used in groups of 5 in order to make a dollar exactly, so we must have exactly 75 pennies. Thus, we need 75 pennies and two coins that add to a quarter, but there are no such coins.