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