Question 504518: If the post office only has stamps of the denominatations 5 and 7 cents, what amount of postage can you buy? Is it a formula?
Same with 3 and 5 as well as 15 and 18
Answer by richard1234(7193)   (Show Source):
You can put this solution on YOUR website! Obviously you cannot make any amount from 1 cent through 4 cents, nor 6 cents. We can construct a table:
7 = 5*0 + 7*1
8 (impossible)
9 (impossible)
10 = 5*2 + 7*0
11 (impossible)
12 = 5*1 + 7*1, and so on.
23 is the largest amount that cannot be made using 5-cent and 7-cent stamps. This is a "theorem" that has one of the most unusual names I've seen: the Chicken McNugget theorem (named because someone wondered what the greatest number of chicken nuggets one couldn't buy, assuming no one ate or took away any). It basically states that for fixed relatively prime integers m and n, the greatest integer that cannot be represented as the sum of an integer multiple of m and an integer multiple of n is mn - m - n.
http://www.artofproblemsolving.com/Wiki/index.php/Chicken_McNugget_Theorem
|
|
|
