# Count On

## Explorer

#### Fibonacci Puzzles

The Fibonacci Numbers are a sequence of numbers that start with 0 and 1. The rest of the series is determined by a simple rule:

So after 0 and 1 we have 0+1 which is 1, again: | 0, 1, 1 |

The latest two are now 1 and 1 so the next number is 1+1=2: |
0, 1, 1, 2 |

and the next will be 1+2: | 0, 1, 1, 2, 3 |

and it continues: | 0, 1, 1, 2, 3, 5, 8, 13, ... |

Here are some puzzles where the answer is "The Fibonacci Numbers"! So, now you
know the solution (!) the puzzle is to work out *why*!!

**Puzzle 1: Brick Wall Patterns**

I have a supply of bricks, where each one is twice as long as it is wide. Suppose I want to use them to make a garden path with them. The path is to be just as wide as one brick is long, or, in other words, the longest side of a brick is the width of the path. What patterns can I make?

The answer depends on how long the path is going to be. We can measure the length of a path using the small side of the brick as 1 "unit". The puzzle is to make a catalogue of all such patterns for paths of different lengths.

**Tip**: Since ordinary dominoes are made up of two squares, they make idea "bricks" to experiment with for this puzzle.

There is only one way to make a path 1 unit long, which is with 1 brick,

but there are two patterns for a path of length 2

and three patterns for a path of length 3.

How many brick patterns can you find for a path of length 4?

**Puzzle 2: Leaping up the stairs**

When I'm in a hurry, I leap up the stairs two at a time - until I get tired and go back to one at a time if it is a *very* long set of stairs. This puzzle is about what patterns of 1-stair and 2-stair combinations I can make to get to the top of flights of stairs of different lengths.

For instance, with a single step there is only one possibility, and therefore is only one pattern. Let's write this down as "1" meaning I just step up 1 stair.

For two steps in the staircase, I can take them singly as in "1" and "1" or I can leap them in a single two-stair jump, which we'll write as "2". So there are two patterns for two stairs.

for three steps, I can again take them all singly:"1" and "1" and "1"

or jump 2 at first and a single step: "2" and "1"

or take a single step and then jump the last two: "1" and "2"

This gives a total of three patterns for three stairs. How many stepping patterns are there for 4 stairs? What about for 5 stairs? or for 6 stairs?

**Puzzle 3: Two heads aren't better than one!**

This game is played by tossing a coin. Each player tosses the coin but, as soon as they have a Head followed by another Head, the game is over. If you have a Head but the next one is a Tail, that is alright and the game continues. So one head on its own is OK, but two heads are fatal!

The winner is the one who has the most tosses before they got two consecutive Heads turning up.

The puzzle is to work out all the ways that a game could last for exactly two tosses, or three tosses, or four and so on. Let's write just H for Heads and T for Tails.

The shortest game is just 2 tosses: | H H |

There is also just one sequence if a game lasted three
tosses: We could not have HHH because then the game would have ended after the second H. |
T H H |

For four tosses, there are just 2 possible games: | H T H H T T H H |

So what about games that last exactly 5 tosses? The last two tosses must have been H's. How many are there?

There are more puzzles of this type at Ron Knott's Fibonacci Puzzles page

.