Thread: 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

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.

Surely there a more... mathematically formulated way?

are you saying do a tree thing??

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?

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.

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.

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?

Originally Posted by hoppingmad

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.

Originally Posted by hoppingmad

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.

No there not... they are 2 different combinations...

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.