1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Coins problem

  1. Feb 25, 2010 #1
    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: Feb 25, 2010
  2. jcsd
  3. Feb 25, 2010 #2
    Can you have negative pennies?
  4. Feb 25, 2010 #3


    User Avatar
    Science Advisor
    Homework Helper

  5. Feb 28, 2010 #4


    User Avatar
    Science Advisor
    Gold Member

    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

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook