Manfred Börgens Mathematische Probleme # 59 |
Liste aller Probleme mit Lösungen
voriges Problem nächstes Problem |
zur Leitseite |
English version |
Niederlande 2001 Michel 1872/73, Block 68 Scott 1068
Dieses Problem erscheint gleichzeitig als Briefmarkenseite # 59.
Die Zahlenfolge des Max Euwe
Die Lösung steht im unteren Teil der Seite.
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 ):
an = q(n2) mod 2 n2 ist die Zahl n als Dualzahl geschrieben. q(.) ist die Bildung der Quersumme. an ist also gleich 0 , wenn n als Dualzahl eine gerade Anzahl Einsen aufweist, und gleich 1 bei einer ungeraden Anzahl Einsen. |
bo = 0 b2n = bn b2n+1 = b*n Sind die ersten 2k Folgenglieder, also bo ... b2k-1 gebildet, so erhält man mit dieser Rekursionsformel die nächsten 2k , also insgesamt 2k+1 Glieder (k ε No). |
co = 0
co ... ci ... c2k-1 --> co c*o ... ci c*i ... c2k-1 c*2k-1 Sind die ersten 2k Folgenglieder gebildet, so erhält man mit dieser Rekursionsformel die ersten 2k+1 Glieder. Dabei wird jede 0 durch 0,1 und jede 1 durch 1,0 ersetzt. Es ist noch zu zeigen, dass sich dadurch die ersten 2k Glieder nicht verändern. |
do = 0 d2k+i = d*i für 0 ≤ i < 2k Sind die ersten 2k Folgenglieder gebildet, so erhält man mit dieser Rekursionsformel die nächsten 2k , also insgesamt 2k+1 Glieder. |
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 an = bn = cn = dn .
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:
Eine Schachpartie wird mit einem Unentschieden beendet, wenn dieselbe Folge von Zügen - mit allen Figuren in genau denselben Positionen - dreimal hintereinander vorkommt. |
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 (dn)nεNo bediente, soll zunächst eine einfache unendliche Zugfolge angegeben werden, die sich als Folge von Nullen und Einsen "codieren" lässt:
Ausgangsposition für die folgenden Springerzüge ist die Anfangsstellung beim Schach. 0 : Sb1 - c3 Sb8 - c6 Sc3 - b1 Sc6 - b8 1 : Sg1 - f3 Sg8 - f6 Sf3 - g1 Sf6 - g8 |
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 (dn)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 (dn)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:
Eine Schachpartie wird mit einem Unentschieden beendet, wenn dieselbe Spielposition mit demselben Spieler am Zug zum dritten Mal wieder auftritt. Eine Schachpartie wird mit einem Unentschieden beendet, wenn in 50 aufeinander folgenden Zugpaaren (weiß-schwarz oder schwarz-weiß) weder ein Bauer gezogen noch eine Figur geschlagen wurde. Es ist erforderlich, dass einer der beiden Spieler das Remis aufgrund einer dieser Regeln einfordert. Dafür hat die FIDE ein genaues Procedere festgelegt. |
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 491/2 Zugpaare liegen dürfen, und dann stehen nur noch die beiden Könige auf dem Brett.
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
Zu 1
an = bn |
Es reicht zu zeigen, dass (an)nεNo die rekursiven Eigenschaften von (bn)nεNo erfüllt:
ao = 0
a2n = q((2n)2) mod 2 = q(n2) mod 2 = an
a2n+1 = q((2n+1)2) mod 2 = (q(n2)+1) mod 2 = ((q(n2)) mod 2)* = a*n
Die jeweils zweite Gleichung in den beiden Rekursionsschritten gilt, weil sich (2n)2 und n2 nur durch eine angehängte Null und (2n+1)2 und n2 nur durch eine angehängte Eins unterscheiden.
an = dn |
Es reicht zu zeigen, dass (an)nεNo die Rekursionseigenschaft von (dn)nεNo erfüllt:
ao = 0
a2k+i = q((2k+i)2) mod 2 = (q(i2)+1) mod 2 = a*i
Im Rekursionsschritt wurde benutzt, dass sich (2k+i)2 und i2 wegen i < 2k nur durch eine vorangestellte Eins unterscheiden.
cn = bn |
Aus der Definition von (cn)nεNo geht nicht unmittelbar hervor, dass es sich überhaupt um eine wohldefinierte Folge handelt, denn bei jedem Iterationsschritt von 2k auf 2k+1 Folgenglieder werden die ersten 2k Glieder (scheinbar) verändert. Also zeigen wir mit vollständiger Induktion über k , dass die ersten 2k Glieder von (cn)nεNo und (bn)nεNo für alle kεNo übereinstimmen:
k = 0 : co = bo = 0
k --> k+1 : Die ersten 2k+1 Glieder:
co c*o c1 c*1 c2 c*2 .... ci c*i ..... c2k-1 c*2k-1 =
bo b*o b1 b*1 b2 b*2 .... bi b*i ..... b2k-1 b*2k-1 =
bo b1 b2 b3 b4 b5 .... b2i b2i+1 .. b2k+1-2 b2k+1-1
Zu 1 a
Die Folge beginnt mit 0110 . Aus der Definition der dn geht hervor, das bei der Rekursion von 2k auf 2k+1 Folgenglieder immer nur die ersten 2k Glieder "gespiegelt" angehängt werden. Die Spiegelung von 0110 ist 1001 , also können nur diese beiden Viererblöcke vorkommen.
Zu 1 b
Wir benutzen zum Beweis die Folge (bn)nεNo : Streicht man alle Folgenglieder mit ungeradem Index, so erhält man (b2n)nεNo = (bn)nεNo .
Zu 2
Wir nehmen an, dass es einen Folgenabschnitt von p Folgengliedern (im folgenden: "p-Kette") gibt, der dreimal hintereinander auftritt.
p = 1 : Ketten 000 und 111 kann es in der Folge wegen 1a nicht geben.
p = 2 : Die dreifache Wiederholung kann nur in vier Formen auftreten, die alle offensichtlich mit 1a kollidieren:
000000
010101
101010
111111
Es gibt aber ein eleganteres Argument, das wir auch für größere p noch anwenden werden. Aus 1b folgt nämlich, dass das Auftreten dreier identischer Ketten hintereinander für p = 2 das gleiche für p = 1 nach sich ziehen würde.
p = 3 : Wie können drei identische 3-Ketten hintereinander in der Folge liegen? Dafür gibt es vier Möglichkeiten, wie die folgende Tabelle zeigt. Die Zellen sind 0110 oder 1001 und die 3-Kette ist ×××.
···· | ×××× | ×××× | ×··· | ···· |
···· | ·××× | ×××× | ××·· | ···· |
···· | ··×× | ×××× | ×××· | ···· |
···· | ···× | ×××× | ×××× | ···· |
Da in jeder Zelle der Tabelle die beiden mittleren Elemente identisch sind, müsste in jeder Zeile × = × = × gelten; aber 3-Ketten 000 oder 111 können nicht auftreten. - Ein alternativer Beweisgang: Listet man die sechs Möglichkeiten für ××× explizit auf, wird offensichtlich, dass sie alle mit 1a kollidieren:
001001001
010010010
011011011
100100100
101101101
110110110
p = 4 : Gleiche Argumentation wie bei p = 2 : Das Auftreten dreier identischer Ketten hintereinander für p = 4 würde das gleiche für p = 2 nach sich ziehen.
p ≥ 5 : Wir zeigen zuerst, dass p gerade sein muss. Die p-Kette enthält sicherlich ein Paar (00 oder 11). Wegen 1a muss das erste Glied eines jeden Paares einen ungeraden Index haben. Wäre p ungerade, würde bei der ersten Wiederholung der p-Kette dieses Paar aber bei einem geraden Index beginnen.
Nun kann man fortgesetzt das Argument von p = 2 verwenden, d.h. die Kettenlänge wiederholt halbieren, bis man bei p < 5 angekommen ist.
Wir haben gezeigt, dass die Annahme falsch war; es gibt also keine Kette, die dreimal hintereinander auftritt.
Publiziert 2007-06-11 Stand 2009-11-10
voriges Problem | Liste aller Probleme mit Lösungen | nächstes Problem