Puzzles on this page have fairly straight-forward
and simple explanations as to why their solution involves the Fibonacci numbers;.
Puzzles on the next page are harder
to explain but they
still have the Fibonacci Numbers as their solutions.
So does a simple explanation exist for any of them?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
Look at the number of patterns you have found for a
wall of length 1, 2, 3, 4 and 5. Does anything seem familiar?
Can you find a reason for this?
Show me an example of why the Fibonacci numbers are the answer
Start by placing n dominoes flat on a table, face down,
and turn them so that all are in the "tall" or "8" position
(as opposed to the "wide" or "oo" orientation). Pack
them neatly together to make a rectangle.
Take the same number of dominoes and, using this rectangle as the picture
to aim at in a jigsaw puzzle, see
how many other flat patterns you can make which have exactly this shape.
This time dominoes can be placed in either the tall or wide direction in your design.
Make a table of the patterns you have found and the number of patterns possible
using 1 domino (easy!), 2 dominoes, 3 dominoes, and so on,
not forgetting to include the original rectangle design too.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
DDD: Three detached houses | |
SD: a pair of semi's first followed by a detached house | |
DS: a detached house followed by a pair of semi's |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
A boat building company makes two kinds of boat:
a canoe, which takes a month to make and
a sailing dinghy and they two months to build.
The company only has enough space to build one boat at a time but it does have plenty of customers
waiting for a boat to be built.
Suppose the area where the boats are built has to be closed for maintenance soon:
How many more ideas can you come up with for a similar puzzle?
length 1 | ||
length 2 | ||
length 3 | ||
length 4 | ||
length 5 | ||
... | ... |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
one rod of length 5: | |||
a rod of length 3 followed by one of length 2: | |||
OR she could put the rod of length 2 first and the 3-rod after it: |
Technically, the collection of sums which total a given
value N are called the
partitions of N.
If, as here, the order of the numbers matters too they are called compositions.
Here we are finding all the compositions of N that do not use the number 1.
It will always be a Fibonacci number!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
If you've ever been to a gathering where there are teachers present, you will know
they always talk about their school/college (boring!). So
we will insist that no two teachers should sit next to each other
along a row of seats and count how many ways we can seat n people,
if some are teachers (who cannot be next to each other) and
some are not . The number of seating arrangements is always a Fibonacci number:
1 chair | or | 2 ways |
2 chairs | or or | 3 ways |
since we do not allow | ||
3 chairs | , , , or | 5 ways |
this time , and are not allowed. |
There will always be a Fibonacci number of sequences for a given number of chairs, if no two teachers are allowed to sit next to each other!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
So we can have ... ... since the two teachers have the other teacher next to them. The non-teacher on the right of these 3 will now also need another non-teacher on his other side so that he too is not left on his own.
A special extracondition in this puzzle is that any seating arrangement must also start with a teacher!
1 chair: | - | 0 ways |
2 chairs: | 1 way | |
3 chairs: | 1 way | |
4 chairs: | or | 2 ways |
5 chairs: | or or | 3 ways |
What happens if we start with a non-teacher always?
What happens if we have no restriction on the first seat?
The answers to these two questions also involve the Fibonacci numbers too!!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
Here is a row of 1 seat which is empty:
and a row of 1 seat which is occupied:
so there are 2 ways to fill a row of 1 seat in this puzzle.
What about a row of 2 seats:
What about 3 seats in a row? and 4?
See Antisocial Dinner Parties by R Lewis in Fibonacci Quarterly 1995, vol 33, pages 368-370.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
If you are on stone number 1, you can only step (s) on to the bank: 1 route.
If you are on stone 2, you can either step on to stone 1 and then the bank (step, step or ss)
OR you can hop directly onto the bank (h):
step | step | ss | |||||
----- hop ----> | h | ||||||
2 sequences |
From stone 3, you can step, step, step (sss) or else hop over stone 2 and then step (hs) or else step on to stone 2 and then hop over stone 1 to the bank (sh):
step | step | step | sss | |||||
----- hop ----> | step | hs | ||||||
step | ----- hop ----> | sh | ||||||
3 sequences |
Why are the Fibonacci numbers appearing?
[With thanks to Michael West for bringing this puzzle to my attention.]
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
For example, for 3 stairs, I can go
1: step-step-step
or else
2: leap-step
or finally
3: step-leap
...a total of 3 ways to climb 3 steps.
How many ways are there to climb a set of 4 stairs? 5 stairs? n stairs? Why?
Adapted from the 1995 third edition (example 2, pages 280-281) of
Applied Combinatorics (4th Edition) by A Tucker, Wiley, 2001, 464 pages.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
The answer is again the Fibonacci numbers. Can you explain why?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
OPTIONAL EXTRA!!! What about the number of sequences of n coin tosses that end with three Heads together? Does this have any relationship to the Fibonacci numbers?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
Price £ | Coin orders | Number of solutions |
---|---|---|
1 | 1 | one way |
2 | 1+1 2 | two ways |
3 | 1+1+1 1+2 2+1 | three ways |
Variation: You are putting stamps on a parcel to make a value of 10 pence but all you have are some 1p and 2p stamps. The stamps are placed in a single row at the top of the parcel.
Follow up: What if we are interested in collections of coins rather than
sequences?
Here 1p+2p is the same collection as 2p+1p since they both contain the
same number of each type of coin.
Mathematicians call a collection that sums to n
a partition of n. They have many
applications in mathematics.
Can you find a simple link between answers to the Change puzzle and your answers to the Stepping Stones puzzle?
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
We could just phone everyone ourselves, so 14 people to share the news with would take 14 separate calls. Suppose each call takes just 1 minute, then we will be on the phone at least 14 minutes (if everyone answers their phone immediately).
Can we do better than this? We could use the speakers on the phone - the "hands free" facility which puts the sound out on a speaker rather than through the handset so that others in the room can hear the call too. For the sake of a puzzle, let's suppose that 2 people hear each call. That would halve the number of calls I need to make. My 14 calls now reduces to 7.
Can we do better still?
Well, we could ask each person who receives a call to not only put the call through the loudspeakers
but also to do some phoning too.
So if two people hear the message, they could each phone two others and pass it on
in the same way and so on. Here's what it looks like if I have 14 people to phone
in this system as the calls "cascade". In the first minute, my first call is heard by
A and B. A's call is heard by both C and D; B's call by E and F, and so on as
in this diagram:
me /------------^----------\ first minute A B /----^----\ /-----^----\ second minute C D E F /--^--\ /--^--\ /--^--\ /--^--\ third minute G H I J K L M NSo all 14 people have heard the news in only 3 minutes! [This is an example of recursion - applying the same optimizing principle at all levels of a problem.]
Can we do even better than this?
Yes - if all the people got together in one room, it would only take one minute!
So let's assume that I cannot get everyone together and I have to use the phone.
Now here is your puzzle. The phones in my company are rather old and do not have an external speaker (and no "conference call" facility) - only one person can hear each call. So I decide that I will phone only two people using two separate calls. I shall give them the news and then ask that they do the same and phone just two more people only. What is the shortest time that the news can pass to 14 people?
me /------------^----\ first minute A \ /----^----\ \ second minute C \ B /--^--\ \ /--^--\ third minute D \ E F \ /--^-\ \ /--^--\ /--^--\ \ ... ... ... ... ... ... ... ...How does the tree continue?
Inspired by Joan Reinthaler's
Discrete Mathematics is Already in the Classroom - But It's Hiding pages 295-299 in:
Discrete Mathematics in Schools,
DIMACS Series in
Discrete Mathematics and Theoretical Computer Science, Volume 36,
American Mathematical Society 1997 .
This is a great book!
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
before: DBCA after : ABCDHere the D has swopped places with the A whilst the B and C have not moved.
Suppose we restrict how we may move (permute) an object to
either fix it, leaving it in the same position
or flip it with a neighbour - two items next to each other swop places (they
cannot now be moved again).
However, not all permutations are made of just these two kinds of transformation. Here are 4 examples of permutations on 4 objects: A, B, C and D:
before: ABCD after : DBCA | This is not a fix-or-flip permutation since the A and D have moved more than 1 place. |
before: ABCD after : ABCD | However, this is since nothing has moved - all 4 items were fixed! |
before: ABCD after : BACD | B and A have flipped and C and D remain fixed and so this is a fix-or-flip permutation. |
before: ABCD after : BADC | All objects have been flipped with a neighbour. |
For 3 objects, ABC, we have 3x2x1=6 permutations:
before: ABC ABC ABC ABC ABC ABC after : ABC ACB BAC BCA CAB CBAOnly the first three are fix-or-flip permutations. In the fourth A has moved more than 1 place and in the last two C has moved 2 places.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
So a natural question is what happens if we have double glazing
which has two sheets of glass separated by an air gap, that is, 4 reflecting surfaces?
Hang on a minute ... what about three surfaces?? Let's look at that first!
For three surfaces (for example two sheets of glass resting on each other) what happens depends on whether we are looking through both sheets of glass (the rays of light come in on one side of the window but exit from the other) or whether we are looking at our own reflection from the sheets (the rays of light enter and leave from the same side of the window).
We can ignore the reflection off the top surface - the light bounces off and we get one reflection. The other cases are the interesting ones - where all the reflections are internal reflections. In other words, the light rays must have actually penetrated the glass and we can get reflections from one or perhaps both or even none of the two internal surfaces. We may even get more reflections as the light bounces off the surfaces again and again, some of the light escaping each time.
The diagram here shows the possible reflections ordered by the number of internal reflections, starting with none (the light goes straight through) to a single internal reflection (from either of the internal surfaces so there are two cases) and then exactly two internal reflections and finally we have shown 3 internal reflections.
If you reflect on this, you'll notice that the Fibonacci numbers seem to be making themselves clearly visible (groan!). Why?
[Advanced puzzle: What does happen with 4 reflecting surfaces in a double
glazed window?]
Reflections across Two and Three Glass Plates by V E Hoggatt Jr and Marjorie Bicknell-Johnson in The Fibonacci Quarterly, volume 17 (1979), pages 118 - 142.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
The reason the puzzles above are "the same" is that the explanation of the solution of each of them involves the Fibonacci (recurrence) Rule:
Suppose we are on a diet but just love chocolate. So we are allowed either a single square or a 2-square piece - one or the other but not both! - and that will be our choice for one day. How many choice patterns are there if we eat chocolate on 2 days?Answer:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ..More..
Fibonacci Home Page
This is the first page on Fibonacci Puzzles. Where to now?
The next page on this Topic: |
The next Topic is... The Mathematical World of Fibonacci and Phi |
© 1996-2006 Dr Ron Knott