Problem: Change for a Dollar (click here to see the problem statement)

---

Change for a Dollar.
My solution.

I first attempted to set up a system of equations; however, I never determined a set of equations that established critical relationships between coin combinations.

I then began to build a table of possible combinations given a starting condition such as 1 Quarter. This did not seem fruitful, that is I was not sure that I came up with a method of systematically establishing all possibilities. It did give me the idea to begin with a starting condition of one coin and determine the maximum total value with some number of one of the other coins.

The table below shows the maximum when starting with 1, 2, or 3 Quarters and the maximum number of either Dimes, Nickels, or Pennies without being able to make change for a dollar:

The table below shows the maximum when starting with Dimes:

In both of the above tables, the largest overall amount obtained is $1.15. Note also that the results in the two tables represent only two combinations that achieve this maximum value.

The table below shows the maximum values when starting Nickels:

Note that none of the totals in the "Nickels" table exceeds $1.15. Also note that the maximum value obtained with a combination of Pennies and another coin is always $.99, so we need not construct a table assuming Pennies as our 'starting' coin.

Again, the greatest overall totals with combinations of two kinds of coins is $1.15:

I assumed this $1.15 to be a "maximum base": I needed to add to this base.

Note that in both cases, the addition of a single Nickel would create the ability to make change for a dollar:

1 Quarter + 1 Nickel + 7 (of the 9) Dimes = .25 + .05 + .70 = 1.00
3 Quarters + 1 Nickel + 2 (of the 9) Dimes = .75 + .05 + .20 = 1.00

I would be in a similar situation should I add 5 or more Pennies. The most I can add then, is four Pennies, for a total of $1.19.