Fibonacci

Fibonacci on the checkerboard (part 2)


You need at least 18 captures in order to rise 5 rows. (Try it yourself).
How many captures are needed (at least) to climb 6 rows? I do not know. I only know from experience that you need at least 48 captures.
Let us skip this problem and concentrate on the next problem: How many captures are needed (at least) to climb 7 rows? See diagram.
In this diagram some of the white squares have got a number. The numbers are powers of µ.
µ = (5 - 1)/2 (the reciprokal value of the golden ratio).           Check that µ² + µ = 1.
Notice that a capture never increases the sum of the numbers beneath the checkers.
We will show that (irrespective of board size) the sum of all numbers beneath the occupied squares is always smaller than 1.
Consequently, there will never appear a checher on the seventh row.
Isn't it amazing.
We will now try to add all numbers beneath the checkers in the starting position. At that stage all checkers are placed behind the red line.



Notice that 1 + µ + µ² + µ³ + ... + µ^k < 1/(1 - µ) for every possible k, or
(1 - µ)(1 + µ + µ² + µ³ + ... + µ^k) < 1.
Proof: (1 - µ)(1 + µ + µ² + µ³ + ... + µ^k) =
1.(1 + µ + µ² + µ³ + ... + µ^k) - µ.(1 + µ + µ² + µ³ + ... + µ^k) =
1 + µ + µ² + µ³ + ... + µ^k - µ - µ² - µ³ - ... - µ^k+1 =
1 - µ^k+1 < 1. q.e.d.

The next step is to add the numbers beneath the "infinite" triangle (formed by diag. a, diag. b, etc).
The sum of the numbers beneath the squares of diag. a is smaller than 1/(1 - µ) as we have just shown.
When you multiply all numbers of diag. a by µ, then you get the numbers of diag. b. (apart from the lengths of the diagonals.)
Thus, the sum of the numbers of diag. b = µ times the sum of the numbers of diag. a, i.e. < µ/(1 - µ).
This shows that the sum of the numbers of the diagonals diag. a, diag. b etc. is smaller than 1/(1 - µ) + µ/(1 - µ) + µ²/(1 - µ) + etc.
Put factor 1/(1 - µ) in front of the expression. This results in (1/(1 - µ)).(1 + µ + µ² + etc.), which is, as we allready know, allways smaller than (1/(1 - µ)).(1/(1 - µ)) = 1/(1 - µ)².
Now regard the numbers of the diagonals diag. 1, diag. 2 etc.
When we multiply the numbers of diag. a by µ⁹, then we obtain the numbers of diag. 1. So, the numbers of diag. 1 are < µ⁹/(1 - µ).
Thus, the sum of the numbers beneath diag. 1 + diag. 2 etc. is smaller than µ⁹/(1 - µ) + µ¹¹/(1 - µ) + µ¹³/(1 - µ) + etc.
Factor µ⁹/(1 - µ) out. That gives: (µ⁹/(1 - µ)).(1 + (µ²) + (µ²)² + (µ²)³ + etc.).
This sum is < (µ⁹/(1 - µ)).(1/(1 - µ²)) = µ⁹/((1 - µ)(1 - µ²)).
The last step is to add the results together and to substract from that result the numbers of the upper triangle (that is the part of the "infinite triangle" above the red line): The sum of all numbers beneath the checkers is 1/(1 - µ)² + 2.µ⁹/((1 - µ)(1 - µ²)) - 1 - 2µ - 3µ² - 4µ³ - 5µ⁴ - 6µ⁵ - 7µ⁶ = {{calculator}}
0,9... < 1.