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

  • Thread starter armolinasf
  • Start date
In summary, the conversation discusses the concept of making perfect change using only 5 and 7 cent stamps. It is determined that the greatest amount that cannot be made using these stamps is 23 cents. The conversation also mentions the steps to prove this and provides a hint for the second part.
  • #1
armolinasf
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
 
Physics news on Phys.org
  • #2
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.
 

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

What is the "Stamp Problem"?

The "Stamp Problem" is a mathematical problem that deals with finding the minimum number of stamps needed to make exact change for any given amount of money. This problem is often used to teach students about the concept of divisibility and can also be applied to real-life scenarios, such as making change at a store.

How does the "Stamp Problem" relate to divisibility?

The "Stamp Problem" relates to divisibility because the solution involves finding the largest possible denominations of stamps that can evenly divide the given amount of money. This concept of finding factors and multiples is essential in understanding divisibility.

Are there any specific strategies or formulas for solving the "Stamp Problem"?

Yes, there are several strategies for solving the "Stamp Problem" depending on the given amount of money. For smaller amounts, it is recommended to start with the largest possible stamp denomination and work downwards. For larger amounts, a more efficient approach is to use the greedy algorithm, which involves continuously subtracting the largest stamp denomination until the remaining amount is 0. There is also a formula, known as the "Stamp Formula", which can be used for larger amounts to find the minimum number of stamps needed.

Can the "Stamp Problem" be solved for any amount of money?

Yes, the "Stamp Problem" can be solved for any amount of money. However, the solution may vary depending on the currency and available stamp denominations. Some amounts may have multiple solutions, while others may not have a solution at all.

What are some real-life applications of the "Stamp Problem"?

The "Stamp Problem" has various real-life applications, such as making change at a store, calculating the minimum number of coins needed for vending machines, and even in the design of computer algorithms for optimizing change-making processes. It is also a popular problem in mathematics competitions and can be used as a fun way to practice basic mathematical concepts.

Similar threads

Optimal Coins for Exact Change Below $1?
Replies
6
Views
2K
Phillip's Phun Phactory: Probability Problem
Replies
2
Views
1K
Combinatorics problem with coins
Replies
6
Views
3K
Solve Basic Algebra Equations & Find Solution Amounts | 3 Significant Figures
Replies
6
Views
2K
Optimization of barrel length in pneumatic cannons
Replies
26
Views
3K
Problem 42 on Gelfand's Algebra (on neighbor fractions)
Replies
7
Views
3K
Solve Stamp Denomination Problems: 1-100 with Up to 3 Stamps
Replies
1
Views
3K
The Relationship Between Masses and Angles in a Pulley System
Replies
29
Views
2K
Confirmation of T/F questions concerning Diodes-Transistors
Replies
4
Views
1K
MATLAB Efficient MATLAB Repeating Function for User-Defined Rotations
Replies
19
Views
2K

Hot Threads

Recent Insights

Back
Top