Printable View
A shopkeeper and her customer each have an unlimited number of coins.
However, they are of only two denominations – 3¢ and 5¢.
1. What amount purchases are not possible using only these two denominations of
coinage, if the shopkeeper is allowed to give change back to the customer?
2. If the shopkeeper has no coins at all to give as change, but the customer has an
unlimited number of these two coins, what purchase amounts are possible?
If the customer started with "a" 3 cent coins and "b" 5 cent coins, and the dealer returned change of "c" three cent coins and "d" 5 cent coins, that is exactly the same as if the customer had "a- c" 3 cent coins and "b- d" 5 cent coins. So we can treat both problems as just "a" 3 cent coins and "b" 5 cent coins as long as we require that both a and b be positive in the first problem, but allow one to be negative in the second.
You are looking for two integers, x and y, such that 3x+ 5y= N for a given integer N. First look at 3x+ 5y= 1. -9+ 10= 1 so one solution is x= -3, y= 2. It is easy to see that x=-3+ 5p and y= 2- 3p is also a solution for any integer p: 3(-3+ 5p)+ 5(2- 3p)= -9+ 15p+ 10- 15p= 1 for all n.
Now, suppose we want to make up "N" cents. Multiply both sides of 3x+ 5y= 1 by N we have 2(Nx)+ 5(Ny)= N so that x= -3N+ 5p and y= 2N- 3p. Now, for what N can we find solutions so that both x and y are positive or where one is positive and the other negative?