Results 1 to 4 of 4

Math Help - Sum of two postage stamps: Part One

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    Sum of two postage stamps: Part One

    This is an academic question that is a little tricker than it appears to be.

    Joe has a big box of 5-cent and 6-cent postage stamps. He wants to determine the amounts of total postage he can create using ONLY 5-cent and 6-cent stamps and the amounts that he CANNOT create using only 5-cent and 6-cent stamps.

    Joe makes the following partial list of postage amounts he can create with only 5-cent and 6-cent stamps:

    5 cents (one 5)
    6 cents (one 6)
    10 cents (two 5's)
    11 cents (one 6 & one 5)
    12 cents (two 6's)
    15 cents (three 5's)
    16 cents (two 5's & one 6)
    17 cents (one 5 & two 6's)
    18 cents (three 6's)
    20 cents (four 5's)

    However, he makes the following list of postage totals that he CANNOT make using only 5-cent and 6-cent stamps:

    7 cents
    8 cents
    9 cents
    13 cents
    14 cents
    19 cents

    For individual stamp values "m" and "n" (which are positive integers) Joe wants to "generalize" the total amounts that he gets (he wants a general statement or rule that describes the relationship between x stamps of value "m", and y stamps of value "n".)

    Can you give a "generalization" and explain why it works?

    Under what conditions will the numbers of stamps of value m and the number of stamps of value n generate all but a finite number of postage amounts? (I.e., a certain finite number of total postage values cannot be created but all others can be.)

    Under these conditions what is a formula for the largest "impossible" postage amount? I.e., a formula for the largest amount that Joe cannot create.

    Thanks for any help anybody can give me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,443
    Thanks
    1863
    In order that a positive integer X be a sum of 5 and 6 cent stamps, there must exist positive integers m and n such that 5m+ 6n= X. That's a "Diophantine equation". It is clear that 6- 5= 1 so 6X+ 5(-X)= X. That is, m= -X and n= X are solutions. Of course, -X is not a positive integer. But if we add 6A to m subtract 5A from n, for A any integer, 5(-X+ 6A)+ 6(X- 5A)= -5X+ 30A+ 6X- 30A = X for all A. We want -X+ 6A\ge 0 or A\ge X/6. But we must also have X- 5A\ge 0 or X\le X/5. That is, X/6\le A\le X/5, recalling that A must be an integer. In particular, that means, in particular, that if X/5 and X/6 differ by at least 1, there exist such an integer. So the first requirement we have is that X/5- X/6\ge 1 from which, multiplying on both sides by 5(6)= 30, we can always form such a combination if 6X- 6X= X\ge 30. That does not mean that every number below that can't be formed by 5 and 6 cent stamps but gives us an upper bound so we can start just working down from that:
    29= 4*6+ 5 so 29 cents is 4 six cent and 1 five cent stamp.
    28= 6+ 22 and 22 is not a multiple of 5
    28= 12+ 16 and 16 is not a multiple of 5
    28= 18+ 10 so 28 cents is 3 six cent stamps and 2 five cent stamps.

    27= 6+ 21 and 21 is not a multiple of 5
    27= 12+ 15 so 27 cents is 2 six cent stamps and 3 five cent stamps.

    26= 6+ 20 so 26 cents is 1 six cent stamp and 4 five cent stamps.

    25= 5 five cent stamps.

    24= 6 six cent stamps.

    23= 6+ 17 and 17 is not a multiple of 5
    23= 12+ 11 and 11 is not a multiple of 5
    23= 18+ 5 so 23 is 3 six cent stamps and 1 five cent stamps.

    22= 6+ 16 and 16 is not a multiple of 5
    22= 12+ 10 so 22 is 2 six cent stamps and 2 five cent stamps

    21= 6+ 15 so 21 is 1 six cent stamp and 3 five cent stamps

    20 is 4 five cent stamps

    19= 6+ 13 and 13 is not a multiple of 5
    19= 12+ 17 and 17 is not a multiple of 5
    19= 18+ 1 and 1 is not a multiple of 5

    Whew! We have determined that every number larger than 19 can be found as a combination of 5 and 6.
    Last edited by HallsofIvy; March 24th 2009 at 05:11 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    9

    Syntax Error, Clarify??

    HallsofIvy,

    Sir, your excellent post has a syntax error message.

    Could be something important has been omitted. It reads as follows:

    *So the first requirement we have is that [ LaTeX Error: Syntax error ]*

    Any chance you could clarify??

    Regards,

    MathGeezer
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,443
    Thanks
    1863
    Thanks for pointing that out. I have editted it. (I used "\" when I should have had "/"!)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Stamps World Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 29th 2011, 09:12 AM
  2. Postage Stamp Problem - Maximum amount of stamps
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2010, 01:53 AM
  3. Induction for postage stamps
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 6th 2010, 03:57 AM
  4. stamps problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 2nd 2010, 09:44 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