No label defined (Q3840765)

Betrachtet wird das folgende Zwei-Personen-Spiel: Gegeben seien \(k\) natürliche Zahlen \(s_1<s_2<\cdots <s_k\), welche die zulässigen Züge beider Spieler definieren, und eine Zahl \(n\in\mathbb{N}_0\), die als Haufengröße bezeichnet wird. Die Spieler verringern abwechselnd die momentane Haufengröße um einen aus der Zugliste \(L= (s_1, s_2,\dots, s_k)\) gewählen Betrag. Jedes Spiel endet. Es gilt für den Spieler als verloren, der die Haufengröße mit seinem Zug negativ machen müßte. Solch ein Spiel wird als Subtraktions-Spiel bezeichnet. Wenn es optimal gespielt wird, -- das heißt, der Spieler, der gewinnen kann, erzwingt dies auch -- dann bestimmt bereits die Haufengröße zu Beginn, ob der anziehende oder der nachziehende Spieler das Spiel gewinnen wird. Für eine gegebene Menge \(L\) nennen wir die Haufengröße \(n\) eine \({\mathcal P}\)- oder \({\mathcal N}\)-Position, je nachdem, ob der Spieler, der am Zug ist, einen Gewinn (positiv) erzwingen kann oder nicht (negativ). Ich betrachte nun die Folge dieser \({\mathcal P}\)- und \({\mathcal N}\)-Positionen für gegebenes \(L\), wobei \(n\) die natürlichen Zahlen durchläuft. Es ist bekannt, daß diese Folge \((v_L(n))^\infty_{n= 0}\) nach höchstens \(2^{\max L}\) Werten periodisch wird, da die Berechnungsformel für \(v_L(n)\) als Schieberegister der Länge \(\max L\) aufgefaßt werden kann. Diese Arbeit stellt neue Ergebnisse der Untersuchung von Subtraktions-Spielen mit Blickrichtung auf lange Perioden dar -- ``lang'' im Verhältnis zu dem größten zulässigen Zug \(\max L\). Es werden auch weitere Aspekte von Subtraktions-Spielen untersucht und Verallgemeinerungen in Hinblick auf Schieberegister angesprochen. Als Hauptergebnisse der Arbeit möchte ich in der Reihenfolge der von mir erarchteten Bedeutung für diesen Zweig der Mathematik nennen: (1) Die wesentlich verbesserte Einschätzung der Periodenlängenverteilung von endlichen Subtraktions-Spielen, insbesondere der 3-Zug-Spiele. (2) Die Einführung des Begriffes der `symmetrischen Zugmengen', deren Identifizierung und Charakterisierung. (3) Die Erstellung eines Konsistenz-Verifizierungs-Programmes für eine Teilmenge von Subtraktions-Spielen. (4) Das Erhärten der Vermutung der Existenz von in ihrer Periodenlänge exponentiell wachsenden Familien von Subtraktions-Spielen. (5) Ein kombinatorischer Beweis einer schärferen oberen Schranke der Periodenlängen für eine große Menge von Subtraktions-Spielen.