Fibonacci

Trees and bits (part 2)

Again, let us dwell on the subject of the family tree as treated in introduction.



This is the family tree of a couple of rabbits in the problem of Fibonacci. A 0 represents a pair of newborn rabbits, and a 1 represents a couple of, at least 1 year old, rabbits. At the same time the picture representent the family tree of a drone. A 0 represents a drone and a 1 represents a female bee.


The n-th row (n>1) of the family tree (from the root) is composed of the first F_n characters from the infinite sequence 1 0 1 1 0 1 0 1 1 0 1 1 ....
The k-th character of this sequence is denoted by f(k). For which k is f(k) = 1? Well, for k = 1,3,4,6,8,9,11,...
We have shown that the i-th number of 1,3,4,6,8,9,11,... is [i].
This sequence is equal to the sequence a₁, a₂, a₃, ... from the preceding section. The sequence b₁, b₂, b₃, ... contains all numbers that do not appear in the a-sequence.

Two players, A(nn) en B(ill), are sitting at table. In front of them there are two heaps of beermats.
In turn, Ann starts, they have to take a number of beermats from the heaps. The person who takes the last beermat wins.
The have to obey the following rules:
They may take an arbitrary number of mats from one of the heaps, or an equal number of mats from both heaps. Is there a winning strategy for one of the players?

The answer is Bill can allways win when at the beginning one of the piles contains a_n mats and the other b_n (for certain n), otherwise Ann can win.
What does Bill have to do when one of the heaps contains a_n mats and the other b_n and when it is Ann's turn? When Ann takes an equal number of mats from both heaps or some of the a_n-mats from one of the heaps, then Bill can allways able to take so many mats from the other pile, that the resulting heaps contain a_j and b_j mats for certain j. When Ann takes away some mats from the heap of b_n mats, then Bill is able to take so many mats from both heaps, that the remaining heaps contain a_j and b_j mats for certain j.

This somewhat complicated rule can be made more transparent by regarding a completely different game!
In turn A(nn) and B(ill) have to move the same queen on a chessboard. The queen may only be moved in the directions south, west or south-west. The person who can put the queen on the square (0,0) (i.e. A1) wins. The startposition of the queen is arbitrary.
Note: It is not necessary to restrict ourselves to a small board like a chessboard. For example, we could take a 100x100 board.
The congruence with the preceding game is as follows:
When the queen is on square (3,7) (in chessjargon: on d8) then this corresponds with 1 heap of 3 beermats and 1 heap of 7 biermats.
A south-west move corresponds with 'take from both heaps an equal amount of mats'; a west-move with 'take some mats from the heap containing 3 mats', and a south-move with 'take some mats from the heap containing 7 mats'.
The three lines through square (0,0) in the chessboard diagram go through exactly those squares from where a player can win in one move.
The red squares on (2,1) and (1,2) are the squares from where a player can only move to a square which has been visited by a red line. Thus when it is your turn and the queen is placed on a red square, then you allways loose.
The 3 lines starting from (2,1) and (1,2) are the lines through all squares from where a player can move the queen in 1 move to the red squares (1,2) or (2,1). Thus again, these are winning positions. We may continue in this way and find all winning and loosing places.

The numbers a_n and b_n can be read from this chess diagram. The solution from the preceding section corresponds with the solution of the chess diagram.