Manfred Boergens - Mathematical Problems

Manfred Börgens
Mathematical Problems

problem list
previous problem next problem

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^* = 1 - x (exchange of 0 and 1).

a_n = q(n₂) mod 2
n₂ is 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 a_n = 1 if n₂ contains an odd number of 1s.

b_o = 0 b_2n = b_n b_2n+1 = b^*_n
This recursion formula takes the first 2^k sequence members b_o ... b_2^k-1 to generate the next 2^k members.

c_o = 0 c_o ... c_i ... c_2^k-1 --> c_o c^*_o ... c_i c^*_i ... c_2^k-1 c^*_2^k-1
This recursion formula takes the first 2^k sequence members c_o ... c_2^k-1 to generate the next 2^k members. Each 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^k sequence members unchanged.

d_o = 0 d_2^k+i = d^*_i for 0 ≤ i < 2^k
This recursion formula takes the first 2^k sequence membegeneraters d_o ... d_2^k-1 to generate the next 2^k members.

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:

Problem # 1 a
The sequence is built of 4-blocks. Each of these blocks is 0110 or 1001 .

Problem # 1 b
The sequence stays unchanged when we eliminate every second member (all members a_n with odd n ). This elimination can be repeated.

This sequence was defined and applied by several mathematicians. If all of them should be honoured its name would be Prouhet-Thue-Morse-Hedlund-Euwe sequence. Its history leads into some very different mathematical topics: Eugène Prouhet (1817 - 1867) used the sequence in number theory (1851) but his results were not noticed for a long time. Axel Thue (1863 - 1922) defined it for a combinatorical problem (1906). As Thue's paper was written in Norwegian, Harald Calvin Marston Morse (1892 - 1977) and Gustav A. Hedlund (1904 - 1993) had no knowledge of it when they again defined the sequence (Morse in differential geometry (1921) and in a joint paper (1944) with Hedlund discussing properties and applications of the sequence). Euwe defined the sequence in a paper about chess rules (1929).

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:

Is chess a finite game ?

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 Mengentheoretische Betrachtungen ueber das Schachspiel several rules were discussed which should restrict every chess game to a finite number of moves. One of them - which prompted Euwe to his investigation - was the rule:

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 d_n . It is easy to design a sequence of chess moves denoted by "0" and another sequence denoted by "1" which both at their end leave the pieces unchanged and in their previous positions, and which consequently can be combined to an infinite sequence. I will give an example for the start position of chess games. Only knights are involved:

0 : b1 - c3 b8 - c6 c3 - b1 c6 - b8 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.

Problem # 2
Prove the sequence d_n to be free of triplets.

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¹/₂ 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