Page 1 of 4 1234 LastLast
Results 1 to 15 of 59

Math Help - help with induction

  1. #1
    Senior Member
    Joined
    Sep 2009
    Posts
    300

    help with induction

    Find the smallest number m such that postage of exactly n cents can be made using only 3-cent and 8-cent stamps for all n>=m. Prove your claim using simple and complete induction.

    I am confused about this question.
    If n is the amount of cents made from the two stamps, wouldn't the smallest m be 0 for all n?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Sneaky View Post
    wouldn't the smallest m be 0
    No. How you gonna make 1 cent postage with only 3 and 8 cent stamps?

    Be clear of the problem. On first glance, I take the problem to be:

    Find the least natural number m such that
    for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k.
    Last edited by MoeBlee; May 23rd 2011 at 12:16 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    I was also wondering if this question implies that 0 amounts of a stamp can be used?

    Also can you explain your reasoning and this question more, for some reason I am not understanding what the question is asking.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    When you say
    Can't be 14 (no way to get 3j+8k=14).

    Then what about:
    3(2)+8(1)=14


    And wouldn't m be 11, because the smallest n would be 11 since 1 of 3-cent stamp and 1 of 8-cent stamp, this is assuming you can't have 0 amounts of a stamp.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Sneaky View Post
    I was also wondering if this question implies that 0 amounts of a stamp can be used?
    Doesn't matter.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    what about:

    Quote Originally Posted by Sneaky View Post
    When you say
    Can't be 14 (no way to get 3j+8k=14).

    Then what about:
    3(2)+8(1)=14


    And wouldn't m be 11, because the smallest n would be 11 since 1 of 3-cent stamp and 1 of 8-cent stamp, this is assuming you can't have 0 amounts of a stamp.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Sneaky View Post
    When you say
    Can't be 14 (no way to get 3j+8k=14).
    I was wrong. I edited it out.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Darn, forget my post I just posted here. I got mixed up myself.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    11 doesn't work. There is no j and k such that 3j+8k=13.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    ohh so what this question is asking is that:

    for all n >= to a certain number, m, there is a perfect combination of 3 and 8 cent stamps?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    So how would I go about solving this problem?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    What the question is asking is this:

    Find the least natural number m such that for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k. And prove that the m you found is indeed the the least natural number m such that for all natural numbers n >= m, there are natural numbers j and k such that n = 3j+8k.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    One way is to go through the natural numbers eliminating them one by one as they fail to be such an m. Then when you get to one that seems to work, prove that it does.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    suppose we could make 3 consecutive integers in such a fashion: m, m+1, and m+2.

    adding a 3-cent stamp to each configuration would then give m+3, m+4, and m+5.

    can you see that we can use induction to show we can make all integers ≥ m this way?

    what are the smallest 3 consecutive integers we can make?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Sep 2009
    Posts
    300
    i think i know it


    14 = 2(3)+1(8)
    15 = 5(3)+0(8)
    16 = 0(3)+2(8)
    17 = 3(3)+1(8)
    18 = 6(3)+0(8)
    19 = 1(3)+2(8)
    20 = 4(3)+1(8)
    21 = 7(3)+0(8)
    22 = 2(3)+2(8)
    23 = 5(3)+1(8)
    24 = 8(3)+0(8)
    25 = 3(3)+2(8)
    26 = 6(3)+1(8)
    (i also see a pattern where the multiplier for 8 is 1,0,2,1,0,2... and for 3 its, +3,-5,+3, +3,-5,+3, +3,-5,+3, +3,-5,+3)

    with a combination of 3 and 8 cent stamps to get one more, you can either remove a 8-cent stamp and put in 3 3-cent stamps or remove 5 3-cent stamps and put in 2 8-cent stamps. Therefore the smallest number is 14.

    Is this the right way to get 14, or do I have to show some formal way, since here i am just assuming it?




    so
    if i set it up like
    3j+8k = n
    then
    3j'+8k'=n+1
    then two cases:

    case 1:
    if k>=1
    remove a 8-cent stamp and put in 3 3-cent stamps
    so
    k'=k-1
    j'=j+3
    then k' and j' are in N
    and
    3j'+8k'=n+1

    case 2:
    if k=0

    3j>=14
    j>=14/3
    j>=5

    remove 5 3-cent stamps and put in 2 8-cent stamps
    so
    k'=k+2
    j'=j-5
    then k' and j' are in N
    and
    3j'+8k'=n+1

    Is this is basic informal correct method?
    Last edited by Sneaky; May 23rd 2011 at 03:23 PM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 4 1234 LastLast

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 11th 2010, 03:08 AM
  3. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 06:12 PM

Search Tags


/mathhelpforum @mathhelpforum