deutsche Version

Max Euwe's sequence

          Solution: See lower part of this page.

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).

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:

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:

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

Problem # 1

We shall prove that  a_n  has the recursive property of  b_n :

a_o = 0
a_2n = q((2n)₂) mod 2 = q(n₂) mod 2 = a_n
a_2n+1 = q((2n+1)₂) mod 2 = (q(n₂)+1) mod 2 = ((q(n₂)) mod 2)^* = a^*_n

The second equation in both recursion steps holds because  (2n)₂  and  n₂  only differ by an appended 0, and  (2n+1)₂  and  n₂  only differ by an appended 1.

We shall prove that  a_n  has the recursive property of  d_n :

a_o = 0
a_2^k+i = q((2^k+i)₂) mod 2 = (q(i₂)+1) mod 2 = a^*_i

This is true because  i < 2^k , so  (2^k+i)₂  and  i₂  only differ by an added 1 at the first position (and maybe some added 0s behind this 1).

Is  c_n  a well-defined sequence? We have to prove that each iteration step using  2^k  sequence members for defining  2^k+1  members leaves the first  2^k  members unchanged. This is done by induction. For each  k  and  n = 0 ... 2^k - 1  we will demonstrate that  c_n = b_n :

k = 0 :   c_o = b_o = 0
k --> k+1 :    The first  2^k+1  members:
c_o c^*_o c₁ c^*₁ c₂ c^*₂ .... c_i c^*_i ..... c_2^k-1 c^*_2^k-1  =
b_o b^*_o b₁ b^*₁ b₂ b^*₂ .... b_i b^*_i ..... b_2^k-1 b^*_2^k-1  =
b_o b₁  b₂ b₃  b₄ b₅ .... b_2i b_2i+1 .. b_2^k+1-2 b_2^k+1-1


Problem # 1 a

The sequence starts with  0110 . The definition of  d_n  shows that in the recursive step from  2^k  to  2^k+1  sequence members the first  2^k  members are appended as binary complement. As  0110  has the binary complement  1001  these two 4-blocks are the "building stones" of the sequence.


Problem # 1 b

Look at the definition of  b_n :  Eliminating all  b_n  with odd  n  yields the sequence  b_2n = b_n .


Problem # 2

Let's assume that the sequence contains a p-chain (a sequence part with  p  members) which is repeated three times successively.

p = 1 :  Chains  000  or  111  cannot occur (see problem # 1 a).

p = 2 :  The threefold repetition can only occur in four variations all of which are impossible (see problem # 1 a):

000000
010101
101010
111111

But there is a more elegant proof which we will also use for larger  p . From problem # 1 b is deduced that three identical successive chains for  p = 2  would lead to three identical successive chains for  p = 1 .

p = 3 :  There are four possible positions for three identical successive 3-chains. This is shown in the following table. The table cells contain  0110  or  1001  and the 3-chain is  ×××.

In every table cell the middle two elements are identical. That means  × = × = ×  ; but 3-chains  000  or  111  cannot occur.  -  Another proof is: There are six possible  ×××  but all of them cannot occur (see problem # 1 a):

001001001
010010010
011011011
100100100
101101101
110110110

p = 4 :  We use the elegant proof method from  p = 2 :  Three identical successive chains for  p = 4  would lead to three identical successive chains for  p = 2 .

p ≥ 5 :  We show first that  p  must be even. The p-chain must contain a pair (00  or  11). Problem # 1 a shows that the first element of every pair must be at an odd position. If we assume  p  to be odd the first repetition of the p-chain would begin at an even position. So  p  is even.
Now the proof method from  p = 4  is used again in an iterative process. The chain length is halved several times until  p < 5 .


The assumption at the beginning of this solution  -  that the sequence contains a p-chain which is repeated three times successively  -  was proved to be wrong.