Problem:
Suzanne went to the bank and withdrew . The teller gave her this amount using bills, bills, and bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Note that the amount of money in bills must be a positive multiple of , and the same is true for the bills and the bills. Then the amount of money apart from the bills must be , or . Thus the and bills must total to for . For each of these cases, the number of bills could be any integer from 1 to , with the remainder consisting of bills. Therefore the number of possibilities is
Let , and represent the number of amounts made up of bills, bills, and bills, respectively. Then and each of , and is an integer greater than or equal to 1 . To count the number of positive integer solutions to this equation, consider 8 "stars" (indicated by asterisks) placed in a row, with 7 spaces (indicated by dashes) between pairs of consecutive stars:
Now choose 2 of the 7 spaces between the stars in ways and place vertical bars in those chosen spaces. This partitions the stars into three disjoint pieces, the integers , and . For example, placing a bar between the second and third stars and also the seventh and eighth stars
gives the solution , and . Thus, there are solutions to the equation.
Note: The argument used to count the number of integer solutions in the second solution is called a "stars-and-bars" or "sticks-and-stones" argument.
The problems on this page are the property of the MAA's American Mathematics Competitions