Results 1 to 3 of 3

Math Help - Postage Stamp Problem - Maximum amount of stamps

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    18

    Postage Stamp Problem - Maximum amount of stamps

    The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

    For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

    Is there an algorithm that given the maximum amount of stamps and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

    Another example:
    Maximum of 5 stamps can be used
    Valued: 1, 4, 12, 21
    The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Celcius View Post
    The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

    For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

    Is there an algorithm that given the maximum amount of stamps and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

    Another example:
    Maximum of 5 stamps can be used
    Valued: 1, 4, 12, 21
    The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.
    For relatively small values, brute force works just fine. Can be implemented recursively. Suppose the max number of stamps is m, and there are n distinct face values. If n^m is about 10^8 or less, naive brute force will be fast enough, and as long as the face values aren't extremely large memory will also not be a problem. Since a+b is the same as b+a, we can restrict to sequences in which terms are (weakly) increasing.

    Edit: Perhaps it's better to use (n+1)^m for thinking of upper bounds on time/memory.
    Last edited by undefined; September 30th 2010 at 10:02 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    An alternative approach could be constructing a table T of breadth m+1 . For every number i, let T[i][j] consist of boolean value "true" if i can be expressed as the sum of exactly m numbers, not necessarily distinct, from the set of n face-values provided, and "false" otherwise.

    Let the given face values be : k_1, k_2, ...., k_n

    It is easy to see that T[0][0] = true, and T[0][j] = false for all other j. Also, for all other i, T[i][0] = false. These are our base cases. For all other i and j, we will use the formula that we derive next.

    If it is possible to represent a number at all with the given face values, then the representation will consist of at least one of those n face values. So, the truth value in T[i][j] will be T[i-k_1][j-1] \cup T[i-k_2][j-1] \cup .... \cup T[i-k_n][j-1] .

    To check whether a number i is representable as a sum of the given face values, we just have to check whether T[i][0] \cup T[i][1] \cup .... \cup T[i][m] is true or not. Here we spend O(nm) time for each number, until we reach the smallest number not representable in the required way, at which point we terminate our algorithm.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What's the maximum amount you should pay to play a game?
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: April 25th 2011, 11:20 PM
  2. Induction for postage stamps
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 6th 2010, 03:57 AM
  3. stamps problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 2nd 2010, 09:44 AM
  4. Sum of two postage stamps: Part One
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 24th 2009, 05:12 AM
  5. Postage Stamps Problem
    Posted in the Math Topics Forum
    Replies: 7
    Last Post: April 12th 2005, 04:40 PM

Search Tags


/mathhelpforum @mathhelpforum