English version

Niederlande 2001        Michel 1872/73, Block 68         Scott 1068


Dieses Problem erscheint gleichzeitig als Briefmarkenseite # 59.



Die Zahlenfolge des Max Euwe


Max Euwe (1901 - 1981) war Niederländer und hieß mit Vornamen eigentlich Machgielis. Sein Mathematikstudium an der Universität Amsterdam schloss er mit der Promotion 1926 ab. Bis 1940 arbeitete er als Gymnasiallehrer. Nach dem Krieg begann Euwe, auf dem jungen Gebiet der Informatik zu forschen, die damals noch als Teil der Mathematik verstanden wurde. Euwe wurde 1954 zum Professor für Kybernetik ernannt. Ab 1959 war er Direktor des niederländischen Forschungszentrums für Automatische Datenverarbeitung. 1964 erhielt er einen Lehrstuhl für Informationsverarbeitung, erst an der Universität Rotterdam, dann an der Universität Tilburg.

Berühmt wurde Max Euwe als Schachweltmeister von 1935 bis 1937. Der Weltmeisterschaftskampf 1935 gegen den amtierenden Weltmeister Alexander Aljechin wurde in mehreren Städten der Niederlande ausgetragen; er war mit 30 Partien einer der längsten WM-Kämpfe aller Zeiten. Er endete mit einem knappen Ergebnis: 9 Siege, 13 Remis, 8 Niederlagen aus Sicht von Max Euwe. Die linke Briefmarke zeigt die Stellung der entscheidenden Partie. Zwei Jahre später eroberte Aljechin den Titel zurück.

Diese Marke würdigt außerdem ein kleines Jubiläum sowie einen Bezug zur Wetterau, der hessischen Region, in der der Friedberger Campus meiner Hochschule liegt: In Bad Nauheim wurde 1937, also vor 70 Jahren, ein Internationales Schachturnier mit Euwe, Aljechin, Bogoljubov und Sämisch ausgetragen, das später in Stuttgart und Garmisch fortgesetzt wurde. Max Euwe gewann dieses Turnier.

Euwe war Präsident der FIDE von 1970 bis 1978. In diese Zeit fiel der WM-Kampf Fischer-Spassky 1972, der wegen des politischen Kontextes (Schach als Stellvertreterkampf der Weltmächte USA und UdSSR mitten im Kalten Krieg) und wegen der schwierigen Persönlichkeiten der beiden Kontrahenten (Fischer war allerdings noch schwieriger als Spassky) Max Euwe viel Fingerspitzengefühl abverlangte, damit dieser Kampf (in Reykjavik) überhaupt stattfinden und bis zum Ende durchgeführt werden konnte.


Euwes Name ist mit einem mathematischen Problem verbunden. Wir betrachten zunächst vier Zahlenfolgen (n ε No), die nur aus Nullen und Einsen bestehen (ist  x  ein Folgenglied, so ist  x*  das "binäre Komplement" zu  x , das Nullen und Einsen vertauscht, also  x* = 1 - x ):

Berechnen Sie die ersten Folgenglieder der vier Folgen. Was fällt Ihnen auf? Genau: Alle vier Folgen sind gleich ! Das kann man natürlich auch beweisen. Also:

Aufgabe 1
Zeigen Sie die Identität  a_n = b_n = c_n = d_n .

Beim Beweis fallen zwei weitere Eigenschaften der Folge auf, die man sich klarmachen sollte, weil sie für Aufgabe 2 verwendet werden können:

1 a
Die Folge besteht aus Viererblöcken, die entweder die Form  0110  oder  1001  haben.

1 b
Die Folge verändert sich nicht, wenn man jedes zweite Element fortlässt (also alle Folgenglieder mit ungeradem Index). Dies lässt sich natürlich beliebig iterieren.


Diese Folge wird mehreren Mathematikern zugeschrieben. Wenn man allen die Ehre erweisen wollte, müsste sie Prouhet-Thue-Morse-Hedlund-Euwe-Folge heißen. Ihre Geschichte zeigt, dass sie Anwendungen in mehreren sehr unterschiedlichen mathematischen Gebieten hat: Eugène Prouhet (1817 - 1867) verwendete sie als erster 1851 in der Zahlentheorie, was aber zunächst unbemerkt blieb. Axel Thue (1863 - 1922) definierte sie 1906 für ein Problem der Kombinatorik. Da Thues Arbeit in Norwegisch verfasst war, kannten Harald Calvin Marston Morse (1892 - 1977) und Gustav A. Hedlund (1904 - 1993) sie nicht, als sie die Folge "wiederentdeckten" (Morse 1921 in der Differentialgeometrie, gemeinsame Arbeit mit Hedlund 1944 zu Eigenschaften und Anwendungen der Folge). Euwe definierte die Folge 1929 erneut, in einer Arbeit über das Schachspiel.

Max Euwe hat diese Folge konstruiert, um eine ganz bestimmte Frage zu den Schachregeln zu beantworten. Diese Frage war offenbar 1929 aktuell und noch offen:

Ist Schach ein endliches Spiel ?

Ob diese Frage "offen" ist, hängt natürlich entscheidend von den Regeln ab. Als Euwe seine Arbeit publizierte, wurden verschiedene Regeln diskutiert, die die Beendigung von Schachpartien in endlich vielen Zügen erzwingen sollten. Eine davon  -  die Euwe zu seiner Arbeit anregte  -  lautet:

Aus wievielen Zügen diese wiederholte Zugfolge besteht, ist bei dieser Regel unerheblich. Offenbar glaubte man, dass eine solche Zugwiederholung früher oder später in jedem Spiel auftritt, das nicht vorher beendet wird. Die Erfahrung der Schachspieler mit sehr langen Partien, in denen keiner der beiden Spieler aufgeben oder in ein Remis einwilligen mag, könnte dafür gesprochen haben. Ein Nachteil dieser Regel ist sicherlich, dass alle Züge aufgezeichnet werden müssen, um das Abbruchkriterium nachweisen zu können  -  vor allem, wenn die dreimal wiederholte Zugsequenz sehr lang ist. Dennoch: Die Regel ist hilfreich, wenn es um die Eindämmung nicht enden wollender Schachspiele geht.  Aber macht diese Regel Schach zu einem endlichen Spiel ?  Nein.  Max Euwe hat in seiner Arbeit von 1929 bewiesen, dass diese Regel nicht das Ende jeder Schachpartie nach endlich vielen Zügen erzwingt. Da er sich dafür der oben definierten Folge  (d_n)_nεNo  bediente, soll zunächst eine einfache unendliche Zugfolge angegeben werden, die sich als Folge von Nullen und Einsen "codieren" lässt:

Die Null steht also für eine Sequenz von vier Damenspringerzügen, die Eins für eine Sequenz von vier Königsspringerzügen; nach jeder dieser Sequenzen stehen alle Figuren wieder in der Ausgangsstellung. Somit codiert jede Folge von Nullen und Einsen eine bestimmte  -  sehr langweilige  -  Schachpartie aus Springerzügen. Selbstverständlich lassen sich realistischere Spielsituationen  -  auch in Endspielnähe  -  angeben, in denen (auch längere) Zugwiederholungen vorkommen können, aber für Euwes Beweis spielt das keine Rolle.

Nun ist der weitere Gedankengang klar: Wenn es eine Folge aus Nullen und Einsen gibt, die "tripelfrei" ist, in der also kein Abschnitt dreimal hintereinander auftritt, dann gibt es eine Schachpartie, die auch bei Gültigkeit der oben formulierten Abbruchregel unendlich lange dauert. Max Euwe, der sich gleichermaßen für Schach und Mathematik begeisterte, fand eine solche Folge, nämlich (d_n)_nεNo . Nun wollen wir auf Euwes Spuren wandeln und die Tripelfreiheit dieser Folge beweisen. Dabei sollen natürlich die Ergebnisse von Aufgabe 1 verwendet werden.

Aufgabe 2
Zeigen Sie, dass die Folge  (d_n)_nεNo  tripelfrei ist, dass also kein Abschnitt der Folge dreimal hintereinander auftritt.

Falls Sie dafür eine kleine Anleitung haben möchten, lesen Sie den Hinweis.


Die von Max Euwe analysierte "Tripel-Regel" ist also aus gutem Grund in den heute aktuellen Schachregeln der FIDE nicht enthalten. Statt dessen sind gleich zwei andere Abbruchregeln in Kraft, die beide unabhängig voneinander garantieren, dass Schach ein endliches Spiel ist:

Es ist offensichtlich, dass diese beiden Regeln "greifen". Bei endlich vielen Feldern und endlich vielen Spielfiguren gibt es nur endlich viele Spielpositionen, auch wenn man noch die Möglichkeiten für en-passant-Schlagen und Rochaden einbezieht, die bei gleicher Stellung der Figuren unterschiedliche Positionen erzeugen können. Daher ist die erste Regel sinnvoll. Durch die zweite Regel werden die Spieler gezwungen, irreversible Züge (Bauern-Ziehen oder Schlagen) zu machen, wenn sie ein Remis vermeiden wollen. In endlich vielen Zügen sind aber diese Züge "aufgebraucht", wenn zwischen ihnen höchstens 49¹/₂ Zugpaare liegen dürfen, und dann stehen nur noch die beiden Könige auf dem Brett.

Lösung



Literatur

Euwe, M.: Mengentheoretische Betrachtungen über das Schachspiel, Proc. Konin. Akad. Wetenschappen (1929) 32 (5), S. 633-642
Stewart, I.: Das unendliche Schachspiel, in: Spektrum der Wissenschaft 7/1996, S. 10-11

Publiziert 2007-05-13          Stand 2009-11-10

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem

Manfred Börgens   |    zur Leitseite