Results 1 to 12 of 12

Math Help - Induction for postage stamps

  1. #1
    Junior Member
    Joined
    Sep 2009
    Posts
    47

    Induction for postage stamps

    I've read a few articles but its not doing the trick.

    can you show step by step how a postage of 12 cents or more can be formed using 4 cents and 5 cents stamps
    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 statman101 View Post
    I've read a few articles but its not doing the trick.

    can you show step by step how a postage of 12 cents or more can be formed using 4 cents and 5 cents stamps
    Ah, you're referring to the fact that the Frobenius number of {4,5} is 4*5-(4+5) = 11.

    The easiest demonstration I can think of involves congruence with a modulus, but you may not be familiar with the notation.

    We can immediately obtain all numbers congruent to 0 (mod 4). These are simply the multiples of 4.

    Starting with 5, we can obtain all numbers congruent to 1 (mod 4). These are numbers of the form 4k+1. Just start with 5 and continue adding 4 to it: 5, 9, 13, 17, ...

    Starting with 10 we can obtain all numbers congruent to 2 (mod 4).

    Starting with 15 we can obtain all numbers congruent to 3 (mod 4).

    So certainly, starting with 15 we can obtain all integers.

    14 we got via 5+5+4. 13 we got via 5+4+4. 12 is 4+4+4. So that accounts for all integers greater than or equal to 12.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by statman101 View Post
    I've read a few articles but its not doing the trick.

    can you show step by step how a postage of 12 cents or more can be formed using 4 cents and 5 cents stamps
    If you are interested in learning math, you need a habit of tinkering by do small experiments such as this:

    4\cdot3+5\cdot0=12
    4\cdot2+5\cdot1=13
    4\cdot1+5\cdot2=14
    4\cdot0+5\cdot3=15
    4\cdot4+5\cdot0=16
    4\cdot3+5\cdot1=17
    4\cdot2+5\cdot2=18
    4\cdot1+5\cdot3=19
    4\cdot0+5\cdot4=20
    4\cdot4+5\cdot1=21
    4\cdot3+5\cdot2=22
    \cdot
    \cdot
    \cdot

    These are: (4q+r)+(5s+t), where q,r,s,t \in \mathbb{N}, and 0\leq r < 4 and 0\leq t < 5

    Now you can prove it by the Strong Principle of Induction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by statman101 View Post
    I've read a few articles but its not doing the trick.

    can you show step by step how a postage of 12 cents or more can be formed using 4 cents and 5 cents stamps
    If some value y is a multiple of fours and fives,
    then

    y=4n+5m

    y+1=4n+1+5m=(n-1)4+4+1+5m=(n-1)4+5+5m=(n-1)4+(m+1)5

    y+2=(n-2)4+4+4+2+5m=(n-2)4+(2)5+5m=(n-2)4+(m+2)5

    y+3=(n-3)4+4+4+4+3+5m=(n-3)4+15+5m=(n-3)4+(m+3)5

    y+4 is a sum of fours and fives if y is.
    y+5 is a sum of fours and fives if y is or if y+1 is.
    y+6 is a sum of fives and fours if y+2 or y+1 is.
    y+7 is a sum of fours and fives if y+3 or y+2 is.

    The pattern repeats.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by statman101 View Post
    I've read a few articles but its not doing the trick.

    can you show step by step how a postage of 12 cents or more can be formed using 4 cents and 5 cents stamps
    Let's have a little fun of writing the proof by the Strong Principle of Mathematical Induction, which says:

    For each positive integer n, let P(n) be a statement If

    (1) P(1) is true and
    (2) \forall k \in \mathbb{N}, P(1)\wedge P(2) \wedge P(3) \wedge...\Rightarrow P(k+1) is true.

    Proof:

    For the basis step, we want to prove the a postage of 12 cents is made of some numbers of 4 cents and 5 cents stamps. So

    We say there exist nonnegative integers a and  b such that 12 = 4a+5b. In fact we have integers a=3 and b=0. So this part of proof is done. We move the next step, the Inductive Step:

    Here we assume the there exist integers a and b such the i=4a+5b, where 0 \leq i <k, where k>12. Now we consider the integer k+1. We show that there are nonnegative integers such that k+1=4a+5b. Since k>12, we we have 13=4\cdot2 + 5 \cdot 1, then we have 14=4\cdot1 + 5 \cdot 2, and we have 15=4\cdot0+5\cdot3. Hence we assume k+1\geq 16. It follows that 12 \leq (k+1) - 4 < k. By the induction hypothesis, there are nonnegative integers a and b such that

    (k+1)-4=4a+5b, and so

    (k+1)=(4a+4)+5b or equivalently, (k+1)=4(a+1)+5b, where (a+1) is and integer.

    This concludes the proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Or...

    P(k)

    y+k=(n-k)4+(m+k)5

    P(k+1)

    (n-k)4+(m+k)5+1 is a combination of integer multiples of 4 and 5 if y+k is

    Proof

    (n-k)4+(m+k)5+1=(n-k)4+(m+k)5+5-4

    =[n-(k+1)]4+[m+(k+1)]5

    bingo
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Sep 2009
    Posts
    502
    This part here is interesting:

    Quote Originally Posted by Archie Meade View Post
    P(k+1)

    (n-k)4+(m+k)5+1 is a combination of integer multiples of 4 and 5 if y+k is

    Proof

    (n-k)4+(m+k)5+1=(n-k)4+(m+k)5+5-4

    =[n-(k+1)]4+[m+(k+1)]5

    bingo
    Why do you have y+k on the left?

    Quote Originally Posted by Archie Meade View Post
    Or...

    P(k)

    y+k=(n-k)4+(m+k)5
    I think the y+k is a little too muddy.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Hi novice,

    sorry about that,
    it's a follow on from my earlier post above,
    i guess they look a bit disjointed,
    i might write out another post.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Archie Meade View Post
    Proof

    (n-k)4+(m+k)5+1=(n-k)4+(m+k)5+5-4<---This here?

    =[n-(k+1)]4+[m+(k+1)]5

    bingo
    While you are at it, I have a question about the line I marked in red.

    It seems that the line in question happened to work out nicely. I am wondering whether that was only an accident.

    In fact the stamps can also be made of some 3 cents and 5 cents stamps. In this particular case, the line in red might even become false.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Since there are so many formal proofs popping up here, I might as well formalise my earlier post.

    Define "k is attainable" as: there exist nonnegative integers m and n such that k = 4m + 5n.

    Base cases:

    12 is attainable, (m, n) = (3, 0).
    13 is attainable, (m, n) = (2, 1).
    14 is attainable, (m, n) = (1, 2).
    15 is attainable, (m, n) = (0, 3).

    Induction step:

    Let k be an integer such that k-4 is attainable. Then k is attainable.

    Proof:

    There exist nonnegative integers m and n such that k-4 = 4m + 5n.

    Then k = 4(m+1) + 5n.

    Therefore, k is attainable.

    One approach to tie together the induction step with the base cases is to use strong induction, but why not just partition the set of nonnegative integers by congruence (mod 4)?

    S0 = {0, 4, 8, ...}
    S1 = {1, 5, 9, ...}
    S2 = {2, 6, 10, ...}
    S3 = {3, 7, 11, ...}

    It can be seen that the intersection of the sets is the empty set, and the union of the sets is the nonnegative integers.

    So we treat each subset the same way we would treat the nonnegative integers and apply weak induction four times.

    Therefore, all integers greater than or equal to 12 are attainable.

    This concludes the proof.
    Last edited by undefined; May 5th 2010 at 08:13 PM. Reason: typo!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by undefined View Post
    Since there are so many formal proofs popping up here, I might as well formalise my earlier post.

    Define "k is attainable" as: there exist nonnegative integers m and n such that k = 4m + 5n.

    Base cases:

    12 is attainable, (m, n) = (3, 0).
    13 is attainable, (m, n) = (2, 1).
    14 is attainable, (m, n) = (1, 2).
    15 is attainable, (m, n) = (3, 0).

    Induction step:

    Let k be an integer such that k-4 is attainable. Then k is attainable.

    Proof:

    There exist nonnegative integers m and n such that k-4 = 4m + 5n.

    Then k = 4(m+1) + 5n.

    Therefore, k is attainable.

    One approach to tie together the induction step with the base cases is to use strong induction, but why not just partition the set of nonnegative integers by congruence (mod 4)?

    S0 = {0, 4, 8, ...}
    S1 = {1, 5, 9, ...}
    S2 = {2, 6, 10, ...}
    S3 = {3, 7, 11, ...}

    It can be seen that the intersection of the sets is the empty set, and the union of the sets is the nonnegative integers.

    So we treat each subset the same way we would treat the nonnegative integers and apply weak induction four times.

    Therefore, all integers greater than or equal to 12 are attainable.

    This concludes the proof.
    Beautiful proof using equivalence classes. I am quite sure there many more ways with Strong induction. Thanks for sharing.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    y=4n+5m

    y+1=(n-1)4+(m+1)5

    y+2=(n-2)4+(m+2)5

    y+3=(n-3)4+(m+3)5

    The base case has y=12 and k=0.

    The general case is P(k) and we use it to establish that it causes P(k+1) to be valid.

    P(k)

    y+k=(n-k)4+(m+k)5 is a combination of multiples of 4 and 5

    P(k+1)

    y+k+1=\left(n-(k+1)4\right)+\left(m+(k+1)5\right) is also a combination of multiples of 4 and 5

    Proof

    y+k+1=\left(n-(k+1)\right)4+\left(m+(k+1)\right)5

    =\left((n-k)4-4\right)+\left((m+k)5+5\right)

    =(n-k)4+(m+k)5+5-4

    which is definately a combination of multiples of 4 and 5 if y+k is.
    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. 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