Coins problem

  • Thread starter rsala004
  • Start date
if you are given an amount of cents, and a set of coin denominations...how can we tell if its impossible to amount to exactly the given amount of cents?

for example say we want to gather 8 units of value but only have coins with denomination 3 and 7, thus its not possible to make a combination that amounts to 8.
(3x + 7y = 8 , has no positive integer solutions)

so given any total , and any set of coin denominations (any # of coins)...how can we tell?


sorry if this sounds trivial...I just can't find a method that suits my need
(ie. computing every possibility won't do the job if the number of coins and total value are large)

I could think of a way to handle the situation given only 2 coins..but any more and the problem becomes unwieldy. its likely just something simple im not seeing
 
Last edited:
Can you have negative pennies?
 

WWGD

Science Advisor
Gold Member
4,174
1,742
This is also called "the stamp problem" : if you have stamps of values p,q only, and
you want to pay for packages beyond a certain amount.

For two coins of values p,q with p,q relatively prime, there is a nice formula for the
largest number that cannot be written as ap+bq ; a,b nonnegative integers:

This highest number is (p-1)(q-1). Assume WLOG p>q . You can show this is
the smallest by producing p consecutive numbers that can be written as
ap+bq.

For more than three rel. prime numbers, this was an open problem recently, and
I think it still is. Try Googling " Postage Stamp" problem for more.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top