Актуализиране на кошницата
Вашата кошница е празна
Fibonacci numbers
Let us start the discussion of combinatorics with an example where during the solution we will become familiar with a method that can often be applied also later when counting the cases. Beside this also an interesting sequence appears.
Example 1
The participants of a summer camp go for an excursion and climb the hill shown in the figure. Two steep footpaths and a twisting path lead up the hill; the twisting path meets the footpaths several times. At these places one can choose to carry on up the steep footpath instead of the twisting path and vice versa (these places are denoted by letters in figure 1). The participants of the camp climbed up the hill starting at the point \latex{A} to the flag at the point \latex{I} so that they always walked either on the twisting path or on one of the steep footpaths. How many of them were there at most if in the end they established that all of them took a different route to the peak of the hill? (Two routes are different if at least one of their segments is different.)
Solution
By starting from the point \latex{A} let us examine in how many different ways we can get to the points denoted by letters. Let us write the number of routes leading to each point next to them. (Figure 1)
To the point \latex{B} we can only get on the twisting path, i.e. in 1 different way.
To the point \latex{C} we can get on the steep footpath from the point \latex{A} or on the serpentine from the point \latex{B}, these are \latex{2} possibilities.
To the point \latex{D} we can go on the serpentine from the point \latex{C} or on the steep footpath from the point \latex{B}. As we could get to the point \latex{C} in \latex{2} different ways, by adding the segment \latex{CD} to these \latex{2} different routes leading to the point \latex{C} two different routes leading to the point \latex{D} are obtained. Only \latex{1} route lead to \latex{B}, thus only \latex{1} route leads to \latex{D} through \latex{B}, that is we can get to \latex{D} in a total of \latex{2 + 1 =} \latex{3} different ways.
\latex{A}\latex{B}\latex{D}\latex{F}\latex{H}\latex{I}\latex{G}\latex{E}\latex{C}\latex{1}\latex{1}\latex{2}\latex{3}\latex{8}\latex{21}\latex{34}\latex{5}\latex{13}Figure 1To the point \latex{E} we can get from \latex{D} or from \latex{C}. By adding the segment \latex{DE} to the \latex{3} routes leading to \latex{D} \latex{3} different routes leading to \latex{E} are obtained, the same way by adding the segment \latex{CE} to the \latex{2} routes leading to \latex{C} \latex{2} different routes leading to \latex{E} are obtained. Obviously different routes leading to \latex{E} are obtained if we walk through \latex{C} or through \latex{D}, thus these \latex{3 + 2 =} \latex{5} routes are all different.
The number of the routes leading to the point \latex{F} is: as we can get to \latex{F} from \latex{E} or from \latex{D}, similarly to the previous calculations we can get to \latex{F} in as many different ways as the sum of the routes leading to \latex{E} and to \latex{D}, i.e. in \latex{5 + 3 =} \latex{8} different ways.
In the same way to the point \latex{G} we can get in as many different ways as to \latex{F} plus to \latex{E}, thus the number of the different routes leading to \latex{G} is: \latex{8 + 5 =} \latex{13}.
Based on this there are \latex{13 + 8 =} \latex{21} different routes leading to the point \latex{H}, and there are \latex{21 + 13 =} \latex{34} different routes leading to the flag at the point \latex{I}.
So if all of them took a different route to the peak, then there could not have been more than \latex{34} of them. If there were exactly \latex{34} of them, then each route was taken by one of the campers.
⯁ ⯁ ⯁
The terms of the Fibonaccisequence:\latex{1; 1; 2; 3; 5; 8; 13; 21; 34; ...}\latex{f_1=1}; \latex{f_2=1}; \latex{f_n=f_{n-1}+f_{n-2}}\latex{\left(n \geq 3\right)}
Let us realise that we could get to any point in as many different ways as we could get to the previous two points together, thus by listing the number of the routes leading to the
points (\latex{A},\latex{B},\latex{C},\latex{D},\latex{E},\latex{F},\latex{G},\latex{H},\latex{I}), the following sequence is obtained:\latex{1},\latex{1},\latex{2},\latex{3},\latex{5},\latex{8},\latex{13},\latex{21},\latex{34}. This sequence can be continued with this method: starting from the third term every term is the sum of the previous two terms. In general the terms of the sequence are:
\latex{f_1=1}; \latex{f_2=1}; \latex{f_n=f_{n-1}+f_{n-2}} \latex{\qquad \left( n \geq 3 \right)}.
It was Fibonacci who first wrote down this sequence in his book Liber Abaci published in \latex{1202}. It was named after him, the Fibonacci sequence, and the numbers constituting the sequence were called Fibonacci numbers.
Originally Fibonacci wrote down this exercise with the following text:
Example 2
A pair of rabbits gives birth to a female and a male rabbit once every month. The little rabbits give birth to their first bunnies two months after their birth. How many pairs of rabbits will there be at the end of the year if there was only one pair of new-born bunnies at the beginning of the year and these did not give birth to bunnies at the end of the first month?
Solution
There is a pair of rabbits at the start of the year, and these rabbits were born at the end of the previous month:
\latex{f_1 = 1}.
There is the same pair of rabbits at the end of the first month, because they give birth only two months after their birth:
\latex{f_2 = 1}.
A new pair of rabbits will be born by the end of the second month, thus
\latex{f_3=2}.
By the end of the third month the original pair of rabbits will have a new pair of new-born bunnies, however the pair of rabbits born in the previous month will not have, thus
\latex{f_4=2+1=3}.
In the fourth month the number of the new-born bunnies of the rabbits from two months earlier should be added to the rabbits from the previous month, thus the total number of the pairs of rabbits is:
\latex{f_5=f_4+f_3=3+2=5}.
In the same way in the fifth month the number of the pairs of rabbits is:
\latex{f_6=f_5+f_4=5+3=8}.
By counting further:
\latex{f_7=13}; \latex{f_8=21}; \latex{f_9=34}, \latex{f_{10}=55}; \latex{f_{11}=89}; \latex{f_{12}=144}; \latex{f_{13}=233}.
So by the end of the year there will be 233 pairs of rabbits.
Exercises
{{exercise_number}}. There is a staircase in front of us that we would like to climb by stepping exactly one stair or exactly two stairs at once. In how many different ways can we get to the third, the fourth, the fifth, the sixth, the seventh and the nth stair when starting from the bottom of the staircase (first step)?
{{exercise_number}}. We would like to paint a building with many floors so that every floor is either completely white or completely blue, but no two adjacent floors can be white. In how many different ways can we paint the building if the number of floors is:
- three;
- four;
- five;
- \latex{n}?
Puzzle
According to the figure an \latex{8 \times 21} rectangle can be dissected as a square with \latex{13}-unit-long sides, therefore their areas are equal, i.e. \latex{168 = 169}. Where is the error?
\latex{8}\latex{8}\latex{5}\latex{13}\latex{13}\latex{8}\latex{5}\latex{8}\latex{8}\latex{5}\latex{5}\latex{8}\latex{8}\latex{8}\latex{8}\latex{5}\latex{5}\latex{13}