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

[armolinasf]

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

 

[verty]

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.