# Fibonacci Proof (Modelling/Abstract Question)

• Nov 24th 2009, 09:43 AM
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 :)
• Nov 24th 2009, 12:07 PM
emakarov
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.
• Nov 24th 2009, 12:55 PM
Surely there a more... mathematically formulated way?

are you saying do a tree thing??
Attachment 14015
Attachment 14014

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

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

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?
• Nov 24th 2009, 01:03 PM
emakarov
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.
• Nov 24th 2009, 01:08 PM
emakarov
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.
• Nov 24th 2009, 01:10 PM
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?
• Nov 24th 2009, 01:13 PM
emakarov
Quote:

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.
• Nov 24th 2009, 01:20 PM
emakarov
Quote:

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.
• Nov 24th 2009, 01:21 PM