• Support PF! Buy your school textbooks, materials and every day products Here!

Stamp Problem

  • Thread starter armolinasf
  • Start date
  • #1
196
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
 

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
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.
 

Related Threads for: Stamp Problem

  • Last Post
Replies
4
Views
982
Top