# FMM3

### From charlesreid1

# 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, |

## Flags

Friday Morning Math ProblemsSpider Socks and Shoes FMM1 Sums of Powers of 2 FMM2 Fifty Coins FMM3 The Zeta Monogram FMM4 The Cthulhus Monogram FMM4B Multiplication Logic FMM5 The Termite and the Cube FMM6 Sharing Dump Trucks FMM7 The Flippant Juror FMM8 Bus Routes FMM9 A Robust Bus System FMM9B Square-Free Sequence FMM10 Inferring Rule from Sequence FMM11 Checkerboard Color Schemes FMM12 One-Handed Chords FMM13 First Ace FMM14 Which Color Cab FMM15 Petersburg Paradox Revisited FMM16 A Binomial Challenge FMM17 A Radical Sum FMM18 Memorable Phone Numbers FMM19 Arrange in Order FMM20 A Pair of Dice Games: FMM21
Category:Puzzles · Template:FMMFlag · e |