Manfred BörgensMathematical Problems |
problem list previous problem next problem |
main page |

deutsche Version |

**Max Euwe's sequence**

Max Euwe (1901 - 1981) was a mathematician and chess world champion. Details of his life can be found on a stamp page of this website. Euwe's name is connected to a mathematical problem. Let's have a look at four sequences containing 0s and 1s. For a sequence member `x` we define `x*` as the "binary complement": `x ^{*}`

a _{n}= q(n _{2})mod 2n is _{2}n written in binary form. q(.) is the sum of the digits. So a _{n}= 0 if n contains an even number of 1s, and _{2}a _{n}= 1 if n contains an odd number of 1s.
_{2} |

b _{o}= 0 b _{2n}= b _{n} b_{2n+1}= b^{*}_{n}This recursion formula takes the first 2 sequence members ^{k}b to generate the next _{o} ... b_{2k-1}2 members.
^{k} |

c _{o}= 0
c _{o} ... c_{i} ... c_{2k-1} --> c_{o} c^{*}_{o} ... c_{i} c^{*}_{i} ... c_{2k-1} c^{*}_{2k-1}This recursion formula takes the first 2 sequence members ^{k}c to generate the next _{o} ... c_{2k-1}2 members. Each ^{k}0 is replaced by 0,1 and each 1 is replaced by 1,0 . It will be shown that this operation leaves the first 2 sequence members unchanged.
^{k} |

for d _{o}= 0 d _{2k+i}= d^{*}_{i}0 ≤ i < 2^{k}This recursion formula takes the first 2 sequence membegeneraters ^{k}d to generate the next _{o} ... d_{2k-1}2 members.
^{k} |

Now compute a few members of the four sequences. You will get a remarkable result: **All four sequences are identical !** We want to prove this:

**Problem # 1
Prove the identity a_{n} = b_{n} = c_{n} = d_{n} .**

The proof of problem # 1 yields - as a by-product - two other properties of the sequence which will be useful for problem # 2:

The sequence is built of 4-blocks. Each of these blocks is

Problem # 1 b

The sequence stays unchanged when we eliminate every second member

This sequence was defined and applied by several mathematicians. If all of them should be honoured its name would be

Max Euwe constructed the sequence because he wanted to solve a certain problem arising in chess. This seems to have been an open question in 1929:

The "openness" of this question depends on the chess rules which have been changed (though not very much) from time to time. When Euwe published his paper

A chess game ends with a draw if a sequence of moves - with all pieces in exactly the same positions - is played three times successively. |

It does not matter how long this sequence is. It seems that chess players believed that a threefold repetition as in the rule will occur sooner or later in every game that is not finished before. Maybe this belief was supported by the experience of very long chess games in which neither player gives up or agrees in a draw. A disadvantage of this rule is that all moves have to be recorded and checked in order to track identical (sometimes very long) move sequences. But nonetheless the rule helps to reduce the number of (seemingly) endless games. **But does this rule make chess a finite game? No.** Max Euwe proved in his paper from 1929 that the rule allows never ending chess games. His proof is based on the sequence

1 : g1 - f3 g8 - f6 f3 - g1 f6 - g8

Naturally, more realistic situations in a chess game - particularly near the end of the game - can be constructed. Now the further proceedings become evident: If we can construct a sequence of 0s and 1s which is free of triplets - no part of the sequence occurs three times successively - we can also construct an infinite chess game in which no part occurs three times successively. Max Euwe was interested in mathematics as well as in chess and found such a sequence; look at problem # 2.

Prove the sequence

This is the reason why modern FIDE rules do not include the chess rule in question. There are two other rules in force each of which guarantees chess to be a finite game:

A chess game terminates with a draw when the same position with the same player to move occurs the third time.A chess game terminates with a draw when in 50 successive move pairs (white-black or black-white) no pawn is moved and no piece is taken. In both cases one of the players must ask for the draw. The FIDE rules give precise instructions for this procedure. |

These two rules are obviously effective. The first rule is based on the fact that chess allows only a finite number of positions. The second rule forces the players to make irreversible moves (after 49^{1}/_{2} move pairs at the latest) if they want to avoid a draw. But there is only a finite number of irreversible moves.

Solution

last update 2008-01-23

previous problem | problem list | next problem

Manfred Börgens | main page