Can you solve Martin Gardner's "coin of the realm" puzzle?

The Colossal Book of Short Puzzles and Problems is a 512-page collection of puzzles from the Martin Gardner's beloved Scientific American column. The easier puzzles are at the front of each section, and become more difficult as you progress. Here's one of the easy ones:

In the United States at least eight coins are required to make the sum of 99 cents: a half-dollar, a quarter, two dimes, and four pennies. Imagine yourself the leader of a small, newly independent nation. You have the task of setting up a system of coinage based on the cent as the smallest unit. Your objective is to issue the smallest number of different coins that will enable any value from 1 to 100 cents (inclusive) to be made with no more than two coins.

For example, the objective is easily met with 18 coins of the following values:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90.

Can you do better? Every value must be obtainable either by one coin or as a sum of two coins. The two coins need not, of course, have different values.

Loading...