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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Stamp problem Date
I A problem in combinatorics Jan 17, 2018
B Optimisation problem Jan 11, 2018
I Math papers and open problems Dec 11, 2017