Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Stamp problem

  1. Feb 8, 2005 #1
    this is quite a classic problem i think but im having difficulty finishing it off. If we have two stamps of positive values a and b, (greater than 1), what values can be expressed as a linear combination of these 2 stamps. If the stamps have a highest common factor greater than 1, then there are infinitely many 'bad' numbers. But if the numbers are coprime, after a certain point, all numbers are possible. For instance, with 5 and 8, in the list of possible numbers, you eventually get 28,29,30,31,32, therefore by adding 5's every other number is possible.
    Can anyone help me prove the fact the if you have a and b, with a<b, then eventually you get 'a' consecutive numbers in the list of possibles. (therefore making all subsequent numbers possible).
    Any other angle welcome!
  2. jcsd
  3. Feb 8, 2005 #2
    think the upper limit of not-possible numbers may be ab-a-b on the basis of a number of examples
  4. Feb 9, 2005 #3
    I presume you mean for A and B to be non-negative. Since we have, in the example given, the case of 5(-3) + 8(2) =1, we see that every integer is possible.

    In the example given: 5A+8B =30, and 5A+8B=32, the first case demands that 5 divide B and the second that 8 divides A. So those cases are only solved in non-negative terms with a zero for A or B. Assuming A less than B, to get A successive values, one of them will be divisible by A giving us a zero coefficient for B.

    So I wonder if that was how you are seeing the problem?
    Last edited: Feb 9, 2005
  5. Feb 9, 2005 #4
    yes, a and b must be non-negative, as must the numbers of each i.e. cant have negative numbers of stamps.
  6. Feb 10, 2005 #5
    Well, here is a start: Let B = A+1. Look at series of A terms: (A+1) + A(A-1)=A^2+1; 2(A+1)+A(A-2)=A^2+2...........A(A+1) + A(A-A) =A^2+A.

    This series fulfillls the necessary requirements and starts at (A+1) +A(A-1) =A^2+1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook