Summarium

Betrachtet wird das folgende Zwei-Personen-Spiel: Gegeben seien k natürliche Zahlen s_{1} < s_{2} < ... < s_{k}, welche die zulässigen Züge beider Spieler definieren, und eine Zahl 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}, …, s_{k}) gewählten 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 P- oder 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 P- und N -Positionen für gegebenes L, wobei n die natürlichen Zahlen durchläuft. Es ist bekannt, daß diese Folge (v_{L}(n))_{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 erachteten 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.

Die Fülle der neuen in der Arbeit zusammengetragenen Einzelergebnisse erweitert das Wissen über Subtraktions-Spiele in erheblichem Maße.

2. Die Einführung des Begriffes der symmetrischen Zugmengen, deren Identifizierung und Charakteriserung.

Die symmetrischen Zugmengen erleichtern das Studium von großen Periodenlängen, da die Anzahl der unabhängigen Züge der Zugmenge auf die Hälfte vermindert ist. Trotzdem sind viele der für die Struktur der P-N -Folgen maßgeblichen Eigenschaften der Subtraktions-Spiele — von den Vorperioden abgesehen — in dieser Teilmenge der Subtraktions-Spiele noch vorhanden.

3. Die Erstellung eines Konsistenz-Verifizierungs-Programmes für eine Teilmenge von Subtraktions-Spielen.

Damit konnte erstmalig die Struktur der P-N -Folge von kubisch in ihren Periodenlängen wachsenden Familien von Subtraktions-Spielen bewiesen werden. Es bietet darüber hinaus auch die Möglichkeit, gegebene Strukturbeschreibungen von polynominal in der Periodenlänge bzw. Vorperiodenlänge anwachsenden Subtraktions-Spielen zu verifizieren. Das Programm kann leicht auf andere Arten von Schieberegisterregeln, das sind gewisse Arten von Bildungsgesetzen von Positionsbewertungen v(n), verallgemeinert werden.

4. Das Erhärten der Vermutung der Existenz von in ihrer Periodenlänge exponentiell wachsenden Familien von Subtraktions-Spielen.

Der Beweis der Existenz solcher Subtraktions-Spiele steht noch aus; insbesondere konnte keine solche Familie explizit angegeben werden. Die mittels umpfangreichen Computereinsatzes zusammengestellten Fakten lassen die Existenz jedoch sehr wahrscheinlich erscheinen.

5. Ein kombinatorischer Beweis einer schärferen oberen Schranke der Periodenlängen für eine große Menge von Subtraktions-Spielen.

Dieser Beweis vermittelt eine Beziehung zwischen der abzählenden Kombinatorik und der Graphentheorie. Damit können in Zukunft neue Resultate über die Anzahl unabhängiger Mengen regulärer Graphen die obere Schranke weiter verbessern.