Click here for the original question.
I started to attack this problem systematically by stating the restraints of the problem using current legal tender:
at most 1 half dollar (H);
at most 3 quarters (Q);
at most 9 dimes (D);
at most 18 nickels (N);
5, 10, or 15 pennies (P);
When I noticed that at most 9 dimes can be used, I immediately found a solution. That is, 9 dimes and 10 pennies is 19 coins that make $1.00.
When I noticed that at most 18 N can be used, I immediately found another solution. That is, 18 N and 1 D is 19 coins that make $1.00.
Starting from the larger denominations: if I had 1 H, then I can have at most 1 Q. If I also had 1 D, then the remaining $.15 needs to be made from 16 coins which is impossible. But, if instead of 1 D, I had 2 N, then I found another solution. That is, 1 H, 1 Q, 2 N and 15 P is 19 coins that make $1.00.
Starting again with 1 H but this time with no Q. If I had at least 1 D, then the remaining money needs to be made from the following possibilities:
Case1: 1 D: 17 more coins making $.40;
Case2: 2 D: 16 more coins making $.30;
Case3: 3 D: 15 more coins making $.20;
Case4: 4 D: 14 more coins making $.10.
In each of these cases, a solution would require 5, 10, or 15 P, but no combinations with N would result in a solution. Thus there is no solution including 1 H and 1 D.
Starting with 1 H and at least 1 N (but no Q nor D). Then the remaining money needs to be made from the following possibilities:
Case1: 1 N: 17 more coins (i.e., P) making $.45;
Case2: 2 N: 16 more coins (i.e., P) making $.40;
Case3: 3 N: 15 more coins (i.e., P) making $.35;
Case4: 4 N: 14 more coins (i.e., P) making $.30;
Case5: 5 N: 13 more coins (i.e., P) making $.25;
Case6: 6 N: 12 more coins (i.e., P) making $.20;
Case7: 7 N: 11 more coins (i.e., P) making $.15;
Case8: 8 N: 10 more coins (i.e., P) making $.10;
Case 9: 9N: 9 more coins (i.e., P) making $.05.
Thus Case 8 provides the next solution. That is, 1 H, 8 N and 10 P is 19 coins that make $1.00.
It is easy to notice that there are no more solutions that include 1
H. So starting from 3 Q. If I also had 1 D, then the remaining $.15 needs
to be made from 15 coins which is the next solution. That is, 3 Q, 1 D and
15 P is 19 coins that make $1.00.
Starting again with 3 Q. If I had 2 or more D, then there will be no solution. This is easy to verify.
Starting with 3 Q and at least 1 N (but no D). Then the remaining money needs to be made from the following possibilities:
Case1: 1 N: 15 more coins (i.e., P) making $.20;
Case2: 2 N: 14 more coins (i.e., P) making $.15;
Case3: 3 N: 13 more coins (i.e., P) making $.10;
Case4: 4 N: 12 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 3 Q and no D.
So, starting with 2 Q and at least 1 D. Then the remaining money needs to be made from the following possibilities:
Case1: 1 D: 16 more coins (i.e., N & P) making $.40;
Case2: 2 D: 15 more coins (i.e., N & P) making $.30;
Case3: 3 D: 14 more coins (i.e., N & P) making $.20;
Case4: 4 D: 13 more coins (i.e., N & P) making $.10.
In Case 1: 6 N and 10 P make $.40. Thus, our next solution consists of 2 Q, 1 D, 6 N, and 10 P.
In each of the other cases, a solution would require 5, 10, or 15 P, but no combinations with N would result in a solution. Thus there is no more solutions including 2 Q and D.
So, let's try 2 Q with at least 1 N. Then the remaining money needs to be made from the following possibilities:
Case1: 1 N: 16 more coins (i.e., P) making $.45;
Case2: 2 N: 15 more coins (i.e., P) making $.40;
Case3: 3 N: 14 more coins (i.e., P) making $.35;
Case4: 4 N: 13 more coins (i.e., P) making $.30;
Case5: 5 N: 12 more coins (i.e., P) making $.25;
Case6: 6 N: 11 more coins (i.e., P) making $.20;
Case7: 7 N: 10 more coins (i.e., P) making $.15;
Case8: 8 N: 9 more coins (i.e., P) making $.10;
Case9: 9 N: 8 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 2 Q and no D.
So, let's try 1 Q with at least 1 D. We will need at least 1 N or 5 P to make an even $1.
Case1: 1 D: 17 more coins (i.e., P) making $.65;
Case2: 2 D: 16 more coins (i.e., P) making $.55;
Case3: 3 D: 15 more coins (i.e., P) making $.45;
Case4: 4 D: 14 more coins (i.e., P) making $.35;
Case5: 5 D: 13 more coins (i.e., P) making $.25;
Case6: 6 D: 12 more coins (i.e., P) making $.15;
Case7: 7 D: 11 more coins (i.e., P) making $.05.
Thus Case 1 and Case 5 provide the next solutions. The first one I almost missed, but when I checked my worked I noticed that 1 Q, 1 D, 12 N, and 5 P is 19 coins that equal $1.00. Case 5 has the solution: 1 Q, 5 D, 3 N and 10 P is 19 coins that make $1.00.
Starting again with 1 Q but this time with no D. At least 12 N is necessary since at most 15 P can be used. So, the remaining money needs to be made from the following possibilities:
Case1: 12 N: 6 more coins (i.e., P) making $.15;
Case2: 13 N: 5 more coins (i.e., P) making $.10;
Case3: 14 N: 4 more coins (i.e., P) making $.05.
It is obvious that there is no solution including 1 Q and no D.
Next we need to look at starting with at most 9 D. We already found a solution (#1) from 9 D. So, let's look at 8 D. Then the remaining money needs to be made from the following possibilities:
Case1: 1 N: 10 more coins (i.e., P) making $.15;
Case2: 2 N: 9 more coins (i.e., P) making $.10.
So, it is easy to see that there is no solution that includes 8 D and n N and p P.
What about 7 D. At least 3 N is necessary since at most 10 P can be used. Then the remaining money needs to be made from the following possibilities:
Case1: 4 N: 8 more coins (i.e., P) making $.10;
Case2: 5 N: 7 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 7 D and n N and p P.
What about 6 D. At least 5 N is necessary since at most 10 P can be used. Then the remaining money needs to be made from the following possibilities:
Case1: 6 N: 7 more coins (i.e., P) making $.10;
Case2: 7 N: 6 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 6 D and n N and p P.
What about 5 D. At least 7 N is necessary since at most 15 P can be used. Then the remaining money needs to be made from the following possibilities:
Case1: 7 N: 7 more coins (i.e., P) making $.15;
Case2: 8 N: 6 more coins (i.e., P) making $.10;
Case3: 9 N: 5 more coins (i.e., P) making $.05.
Thus Case 3 provides the next solution. That is, 5 D, 9 N and 5 P is 19 coins that make $1.00.
Starting again with 4 D. At least 9 N is necessary since at most 15 P can be used. Then the remaining money needs to be made from the following possibilities:
Case1: 9 N: 6 more coins (i.e., P) making $.15;
Case2: 10 N: 5 more coins (i.e., P) making $.10;
Case3: 11 N: 4 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 4 D and n N and p P.
What about 3 D. At least 11 N is necessary since at most 15 P can be used. Actually a maximum of only 5 P can be used so at least 13 N are necessary. Then the only possibility to make up the remaining money is as follows:
Case1: 13 N: 3 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 3 D and n N and p P.
What about 2 D. At least 13 N is necessary since at most 15 P can be used. Actually a maximum of only 5 P can be used so at least 15 N are necessary. Then the only possibility to make up the remaining money is as follows:
Case1: 15 N: 2 more coins (i.e., P) making $.05.
So, it is easy to see that there is no solution that includes 2 D and n N and p P.
Finally, we can look at 2 D but we already have found a solution (#2).
Thus, I have found 8 combinations of 19 U.S. legal tender coins that equal exactly one dollar.
The U.S. has also made coins in the denominations of 1/2 cent (HP), 2 cents (W), and 3 cents (T). If we were to include these, then what additional combinations of 19 coins can make one dollar?
So far, I have found three solutions:
1 H, 1 Q, 1 N, 2 T, and 14 P is 19 coins that make $1.00.
1 H, 1 Q, 1 N, 2 W, 1 T, and 13 P is 19 coins that make $1.00.
1 H, 4 D, 6 P, and 8 HP is 19 coins that make $1.00.
The U.S. has also made gold coins in the denominations of 1 dollar (GD), 2 dollars (GT), and 5 dollars (HE). If we were to include these, then what additional combinations of 19 coins can make ten dollars?
So far, I have found many solutions. This is an analogous problem to the above problem and the first extension. All that is necessary is a movement of the decimal place in the above solutions to check see if it is a solution here! Beware, not all the above solutions have an analogous solution here.