FMM3

Friday Morning Math Problem

Fifty Coins

Find the number of ways that change can be made for $1.00, using exactly 50 coins.

Solution

Denote the number of pennies, nickels, dimes, quarters, and fifty-cent pieces as x1, x5, x10, x25, x50 Now, we know already that x50 = 0, since having even one fifty-cent piece would require us to make 50 cents from 49 coins, which is impossible. We can express the total sum of all the coins as the equation: x1 + 5 * x5 + 10 * x10 + 25 * x25 = 100 (I) Further, we can express the number of pennies in terms of the number of other coins: x1 = 50 - (x5 + x10 + x25) (II) Substituting this into the first equation gives us (one equation with three unknowns): 25 * x25 + 10 * x10 + 5 * x5 + 50 - (x25 + x10 + x5) = 100 (III) or 5 x25 + 2 x10 + x5 - (1/5)( x25 + x10 + x5 ) = 10 (IV) We know a few other things that can help narrow down the space of possible solutions: The value of all of the coins must be a multiple of 5 (as implied by equation I, since the difference of two multiples of 5 is also a multiple of 5). So, the number of pennies x1 is a multiple of 5, and the quantity x25 + x10 + x5 is also a multiple of 5 (by equation II), and therefore the quantity 25 * x25 + 10 * x10 + 5 * x5 is also a multiple of 5 (by equation III). The value of x25 + x10 + x5 > 0 (we know there are no fifty-cent pieces, and we know the case of all pennies will not add up to $1.00, so we need at least one nickel, dime, or quarter) and is a multiplle of 5 (by equation II). We know 25 x25 + 10 x10 + 5 x5 > 50 (by equation III). Now we have greatly reduced the problem space. We know that the number of pennies must be a multiple of 5, somewhere between 5 and 45, and the sum of the face values of the remaining coins must be larger than 50. There are three unknowns x25, x10, x5. We know the number of quarters x25 is 1 or 0, so we can try both values. In the case of x1 = 45 and x25 = 1, we know that there are either 4 (5-1) or 9 (10-1) remaining coins, since x25 + x10 + x5 must be a multiple of 5. We have only a handful of outcomes to try, and (x5 = 2, x10 = 2) satisfies both the inequality 25 x25 + 10 x10 + 5 x5 > 50 and the master equation (I) (that all coins sum to $1.00). In the case of x1 = 40 and x25 = 0, we know that the number of remaining coins is a multiple of 5. No combination of 5 nickels and dimes can satisfy our inequality 25 x25 + 10 x10 + 5 x5 > 50, so we know we need 10 nickels and dimes. Starting with x10 = 2 (the only number of dimes that will satisfy the inequality), we find that 2 dimes implies 8 nickels, which is another solution. x1 = 35 yields no valid solutions, and no other solutions are possible. To decide where to start, we can guess that the number of pennies will be large, so we start with x1 = 45. Furthermore, to save ourselves some time, we know that the number of pennies will be large, so we can start with 45 pennies, and try all the solutions where the number of pennies is less than 50 but a multiple of 5. x1 = 45 implies and x1 = 40 both yield valid solutions, so the total solutions are: 1 quarter, 45 pennies,