Solving the Stamp Problem: Finding the Greatest Amount for Perfect Change

  • Thread starter Thread starter armolinasf
  • Start date Start date
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
1 reply · 2K views
armolinasf
Messages
195
Reaction score
0

Homework Statement



If you have only 5 and 7 cent stamps you can make perfect change of a 5,7,10,15,17, etc. cent letter. You cannot mail a 1,2,3,4,6,8,9,11,etc. cent letter. What is the greatest amount that you cannot make perfect change for?

2.Attempt at a Solution

I'm pretty confident that the answer is 23 cents, however I want to be able to prove that that is in fact the absolute greatest amount for all possible combinations. Thanks for the help
 

Discussion

Physics news on Phys.org
There are two steps to proving it:
A. Prove that 23 cannot be made up of 5 and 7 cent stamps.
B. Prove that every number > 23 can be made up of 5 and 7 cent stamps.

A hint for the second part, only 5 numbers > 23 need to be checked to be sure it is true for all numbers > 23.