Results 1 to 10 of 10

Math Help - Fibonacci Proof (Modelling/Abstract Question)

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    14

    Fibonacci Proof (Modelling/Abstract Question)

    A certain parking meter will accept only $1 or $2 coins (we're Australian... it's okay!). Parking in this regulated areas costs $1 per hour and a maximum time of six hours of parking is allowable. Coins can only be inserted into the meter one at a time, and a sequence of, say $1 + $2 is considered to be a different sequence to $2 + $1.

    Determine the total number of combinations of $1 and $2 coins that are possible when payment is made for up to the maximum of 6 hours.

    I have the combinations (there really aren't many) but this is under Fibonacci proofs and induction and I just can't see how's it relates? Just a couple of hints would be amazing. Please and Thanks guys
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Very nice problem. One hint is to look at the number of ways to pay for exactly n hours. I tried several small n's, and for each n I drew a binary tree. For each node, one child corresponds to paying $1, the other $2. Each tree node may be labeled with the amount left. After doing an exhaustive search of ways to pay in this manner, I noted that some parts of trees for larger n's are copies of trees for smaller n's.

    Of course, this is just what I tried; this may not be the easiest or the most intuitive way to approach the problem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    14
    Surely there a more... mathematically formulated way?

    are you saying do a tree thing??
    Fibonacci Proof (Modelling/Abstract Question)-parkingdiagram.bmp
    Parking Meter Tree Diagram..doc

    So using this I can see there are 13 ways...

    holy moley... that isn't a Fibonacci number I see is it??

    okay so maybe there's a formula to the way?? the 7th Fibonacci number is the answer to make a maximum $6 from 1 and 2 dollar coins...

    Is there are a math formula or something that can be produced?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Nice trees! Though it would be better to write the remaining amount in the nodes.

    So, I understand that if one adds a root to the whole picture, one gets the tree for 6. Well, the top subtree is the tree for 5, and the bottom one is for tree for 4.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    One needs to add a child to one of the $2 nodes in the bottom tree. If you go $2, $1, $2, you have only $5, not $6. After that, the bottom tree for 4 is isomorphic to the top subtree of the top tree.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2009
    Posts
    14
    okay what?

    Yep, I missed another $1.

    Um you mean for the first one go like
    ----4
    5
    ----3

    etc. etc. rather than
    ---1
    1
    ---2


    and your saying where directly behind those purple ones would be the way to get $5, behind that, $4....

    all Fibonacci numbers...

    Except they start at 1.

    there's 1 way to get $1
    2 ways to get $2
    3 ways to get $3
    5 ways to get $4
    etc.

    what's isomorphic?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Quote Originally Posted by hoppingmad View Post
    okay what?

    Yep, I missed another $1.

    Um you mean for the first one go like
    ----4
    5
    ----3

    etc. etc. rather than
    ---1
    1
    ---2
    Yes. Branches should be labeled with $1 or $2, and nodes with the remaining amount. So the sum of branch labels from a node to a leaf must be equal to that node's label.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Quote Originally Posted by hoppingmad View Post
    what's isomorphic?
    In the picture you posted looks like this:

    Code:
          4...
         /
        5
       / \
      6   3...
       \  3...
        4/
         \2...

    The subtrees that have the same label in the root (like the bottom subtree with root 4 and the top subtree of the top subtree also with root 4) are the same.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Oct 2009
    Posts
    14
    No there not... they are 2 different combinations...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    No there not... they are 2 different combinations...
    In both cases you have to spend $4. I don't know how this will show because I use OpenOffice, but I am attaching your drawing. I spoiled it by trying to draw a line around the subtree that is isomorphic to the bottom tree (provided you add a node to the bottom tree where there is a short line).

    Remember that it is not node labels you are after. What is important is the number of leaves -- each leave corresponds to one way to spend $6. This number is the sum of the corresponding numbers for $5 and $4.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Proof II
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2011, 03:04 AM
  2. Fibonacci Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 5th 2009, 08:08 AM
  3. Another Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 11th 2008, 04:17 AM
  4. Fibonacci proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 26th 2007, 07:37 AM
  5. Fibonacci proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2007, 07:36 AM

Search Tags


/mathhelpforum @mathhelpforum