Write down a 0:

0

Now mentally “flip” this string in binary, exchanging 0s and 1s, and append this new string to the existing one:

0 1

Keep this up and you’ll get a growing string of 0s and 1s:

0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
…

This is the Thue–Morse sequence, named after two of its discoverers, Axel Thue and Marston Morse. One interesting property of the sequence is that, no matter how far it’s extended, it contains no “cubes,” no instances in which some nonempty string occurs three times in a row. For example, the last line above contains both 11 and 00 but no instance of 111 or 000. (It also contains 1001 twice in a row, but not three times.)

Max Euwe, the Dutch mathematician who was world chess champion from 1935 to 1937, used this principle to show that chess was not a finite game. Under the rules at the time, a chess game would end in a draw if a sequence of moves (with all pieces in the same positions) were played three times in a row. Euwe used the Thue-Morse sequence to show that this need never happen: If 0 represents one set of moves, and 1 represents another, and each set leaves the board position unchanged, then the Thue-Morse sequence shows that two players might step through these routines forever without ever playing one three times in a row.

Modern chess rules have dropped the threefold sequence provision. Instead a draw results when the same board position occurs three times, or when 50 successive moves occur without a capture or a pawn move. Both of these rules limit a game to a finite length (although one player must actually claim the draw).

(Thanks, Pål.)