Results 1 to 6 of 6

Math Help - Induction Problem

  1. #1
    Junior Member
    Joined
    Feb 2007
    Posts
    44

    Induction Problem

    Suppose you are in a country that has bank notes of value $3 and $5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than $7.

    Thank you for your help in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by MathStudent1 View Post
    Suppose you are in a country that has bank notes of value $3 and $5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than $7.

    Thank you for your help in advance.

    This is the Frobenius coin problem for n=2.
    The general idea is that whenever gcd(3,5)=1 you can go on forever eventually.

    This formula in this case is,
    (x-1)(y-1)=(5-1)(3-2)=8
    Thus, 8 is the smallest number from where everything is obtainable, or you can think of it as 7 is the largest number from which no combination is possible.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by MathStudent1 View Post
    Suppose you are in a country that has bank notes of value $3 and $5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than $7.

    Thank you for your help in advance.
    Suppose that you can make some total n>15, If no 5's are used then convert
    5x3's to 3x5's, So we can always make n with at least 1x5.

    Now add 2x3 and take away 1x5, so we have now made n+1. So if there
    is any total N>15 which we can make with 3's and 5's then by induction
    we have proven that we can make any total n>N.

    Let N=$20, then we can make it as 5x3+1x5, hence we have proven that
    any total >$20 can be made with $3 and $5 bills by induction.

    (Note with a bit more care we can reduce the mimimum sum that can be
    made to the the $8 in ImPerfectHackers post, but the question does not
    ask for a tight lower limit, so we don't need that complication).

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Thank you CaptainBlack. I guess I don't see how this problem is an induction problem? I am familiar with doing induction problems that involve summation or inequalities. Thanks again.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,735
    Thanks
    642
    Hello, MathStudent1!

    I think I can hammer this into an Induction proof . . .


    Suppose you are in a country that has bank notes of value $3 and $5 only.
    Prove that it is possible to pay (without requiring change) for any item
    which is worth a whole number of dollars greater than $7.
    Since the value (V) is greater than 7: .V > 8.


    S(1): The first case is V = 8, which can be made with 3 + 5.


    Assume S(k): that V = k can be expressed as a combination of 3's and/or 5's.


    We must prove S(k+1): that k + 1 can be expressed as a combination of 3's and/or 5's.

    There are two possible cases for the value of k:

    (1) k is a multiple of 3. .Then k = 3a, for some integer a.
    . . .Since k > 8, a must be at least 3. .There are at least three $3 bank notes.
    Then we can create k + 1 by adding two $5 notes and removing three $3 notes.

    (2) k is not a multiple of 3. .There is at least one $5 bank note.
    Then we can create k + 1 by adding two $3 bank notes and removing one $5 dollar bank note.

    In either case, given k dollars, we can create k+1 dollars.


    We have proved that: .S(k) . .S(k+1).
    . . The induction proof is complete.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2007
    Posts
    44
    Thank you Soroban. I am still working on the problem and trying to see it all.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Another induction problem help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 12th 2012, 04:57 PM
  2. induction problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 22nd 2010, 07:28 AM
  3. induction problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 26th 2009, 07:34 AM
  4. induction problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 8th 2009, 09:18 PM
  5. induction problem,
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 7th 2009, 05:57 AM

Search Tags


/mathhelpforum @mathhelpforum