Question 1199424: assuming you had a unlimited supply of 3cent and 7cent stamps what is the largest amount os postage you cannot make?
Answer by ikleyn(52815) (Show Source):
You can put this solution on YOUR website! .
Assuming you had a unlimited supply of 3cent and 7cent stamps,
what is the largest amount of postage you cannot make?
~~~~~~~~~~~~~~~~~~
With 3-cent and 7-cent stamps, the ANSWER is 11 cents.
Indeed, it is easy to check that you can not
combine 11 cents using 3c and 7c stamps, only.
From the other side, it is easy to prove that
you can combine any number of cents greater than 11,
using 3c and 7c stamps.
Indeed, 12 = 4*3; 13 = 7 + 2*3; 14 = 2*7.
Let N be the number of cents, N >= 12.
(a) If N is a multiple of 3, you simply combine N as
the integer number of 3c stamps.
(b) If N >= 12 gives the remainder 1 when divided by 3, then (N-1)
is a multiple of 3, and you can combine N-1 cents using 3c stamps, only.
In this combination, you will have at least four 3c stamps.
Now from this combinations of 3c stamps, take off two 3c stamps and add
one 7c stamp - it will be your desired combination for N cents.
(c) If N >= 12 gives the remainder 2 when divided by 3, then (N-2)
is a multiple of 3, and you can combine N-2 cents using 3c stamps, only.
In this combination, you will have at least four 3c stamps.
Now, from this combinations, take off four 3c stamps and add
two 7c stamps - it will be your desired combination for N cents.
Thus I proved for you that you can combine everything above or equal 12 cents.
So, 11 cents is your answer to this problem.
/////////////////
For more general problem, see well explained solution at this link
https://www.usna.edu/Users/physics/mungan/_files/documents/Scholarship/StampsProblem.pdf
|
|
|