1. What is the smallest number of coins that cannot make change for a dollar? Each coin may be selected to be a silver dollar, half dollar, quarter, dime, nickel, or penny. Examples:

   1 coin		silver dollar
   2 coins		2 halves
   3 coins		half, 2 quarters
   4 coins		4 quarters
   5 coins		half, quarter, 2 dimes, nickel
   6 coins		3 quarters, 2 dimes, nickel	or	half, 5 dimes
   etc.

2. If all you hold are coins of the above possible denominations, what is the largest amount of money you could have and not be able to make exactly one dollar ($1.00)?

3. In how many ways can you make change for a dollar using only coins? (For example: four quarters, OR ten dimes, OR nine dimes and two nickels, OR ...)
   • Can you first show how many ways you can make change for lower multiples of 5 cents?
   • Is there an iterative or combinatorial solution? (i.e. Can you use the results of 50 cents and 25 cents to determine the result for 75 cents?)
   • If you use a computer program, please send it, as well as a simple description of its operation.

Source: 1. David Berthold. 2,3. Many sources.

Kirk sent several different programs (of increasing performance) to find answers to the three questions. Here are the answers, followed by his program:

1. 77 coins is the first number of coins a dollar cannot be decomposed into.
2. $1.19 is the largest amount of money you could hold in coins and not be able to make exactly $1.00. (Ex: 3 Quarters, 4 Dimes, 4 Pennies.)
3. There are 293 different ways to make change for a dollar using coins.

#
# change.c
#
main()
{
int S,H,Q,D,N,P,coins;
float change;

for(S=1;S>=0;S--)
 for(H=2;H>=0;H--)
  for(Q=4;Q>=0;Q--)
   for(D=10;D>=0;D--)
    for(N=20;N>=0;N--)
     for(P=100;P>=0;P--){
      change=(S*1.00)+(H*0.50)+(Q*0.25)+(D*0.10)+(N*0.05)+(P*0.01);
      coins=S+H+Q+D+N+P;
      printf("%4d coins: S:%1d H:%1d Q:%1d D:%-2d N:%-2d P:%-3d = $%04.2f\n",
              coins,S,H,Q,D,N,P,change);
      }
}