In der kombinatorischen Spieltheorie stellt der Sprague-Grundy Lehrsatz fest, dass jedes gerechte Spiel laut der normalen Spiel-Tagung zu einem nimber gleichwertig ist. Der Grundy-Wert oder Nim-Wert eines gerechten Spiels werden dann als der einzigartige nimber definiert, zu dem das Spiel gleichwertig ist. Im Fall von einem Spiel, dessen Positionen (oder summands von Positionen) durch die natürlichen Zahlen (zum Beispiel die möglichen Haufen-Größen in nim ähnlichen Spielen) mit einem Inhaltsverzeichnis versehen werden, wird die Folge von nimbers für aufeinander folgende Haufen-Größen die Nim-Folge des Spiels genannt.

Der Lehrsatz wurde unabhängig von R. P. Sprague (1935) und P. M. Grundy (1939) entdeckt.

Definitionen

Zu den Zwecken des Sprague-Grundy Lehrsatzes ist ein Spiel ein Zwei-Spieler-Spiel der vollkommenen Information, die die endende Bedingung befriedigt (alle Spiele laufen ab: Es gibt keine unendlichen Linien des Spieles), und die normale Spiel-Bedingung (ein Spieler kann sich der nicht bewegen verliert).

Ein gerechtes Spiel ist ein wie nim, in dem jeder Spieler genau dieselben verfügbaren Bewegungen wie der andere Spieler in jeder Position hat. Bemerken Sie, dass Spiele wie tic-tac-toe, Kontrolleure und Schach nicht gerechte Spiele sind. Im Fall von Kontrolleuren und Schach, zum Beispiel, können Spieler nur ihre eigenen Stücke, nicht ihre Gegner bewegen. Und in Tic-Tac-Toe stellt ein Spieler X hin, während der andere O hinstellt. Gerechte Spiele fallen in zwei Ergebnis-Klassen: irgendein die folgenden Spieler-Gewinne (eine N-Position) oder die vorherigen Spieler-Gewinne (eine P-Position).

Ein gerechtes Spiel kann mit dem Satz von Positionen identifiziert werden, die in einer Bewegung erreicht werden können (diese werden die Optionen des Spiels genannt). So ist das Spiel mit Optionen A, B, oder C der Satz {A, B, C}.

Die normale Spiel-Tagung besteht wo der letzte Spieler darin, um Gewinne zu bewegen. Wechselweise verliert der Spieler, der zuerst keine gültige Bewegung hat. Das Gegenteil - die misère Tagung besteht darin, wo die letzte Person, um eine gültige Bewegung zu haben, oder die letzte Bewegung macht, verliert.

Ein nimber ist angezeigter *n eines speziellen Spiels für einen Ordnungsn. Wir definieren *0 = {} (der leere Satz), dann *1 = {*0}, *2 = {*0, *1}, und * (n+1) = *n  {*n}. Wenn n eine ganze Zahl, der nimber *n = {*0, *1..., * (n−1)} ist. Das entspricht einem Haufen von N-Schaltern im Spiel von nim, folglich der Name.

Zwei Spiele G und H können hinzugefügt werden, um ein neues Spiel G+H zu machen, in dem ein Spieler beschließen kann, entweder sich in G oder in H zu bewegen. In der Satz-Notation G+H Mittel {G+h für h in H}  {g+H für g in G}, und so ist Spielhinzufügung auswechselbar und assoziativ.

Zwei Spiele G und G' sind gleichwertig, wenn für jedes Spiel H, das Spiel G+H in derselben Ergebnis-Klasse wie G'+H ist. Wir schreiben G 

Ein Spiel kann sich auf zwei Dinge beziehen. Es kann eine Reihe möglicher Positionen und ihre Bewegungen durch seine Regeln, zum Beispiel, Schach oder nim definieren. Es kann auch auf eine bestimmte Position, zum Beispiel, das Spiel *5 verweisen. Allgemein ist das Vorhaben, genommen zu werden, vom Zusammenhang klar.

Lemma

Für gerechte Spiele, G  G' wenn und nur wenn G+G' ist eine P-Position.

Erstens bemerken wir, dass  eine Gleichwertigkeitsbeziehung ist, da die Gleichheit von Ergebnis-Klassen eine Gleichwertigkeitsbeziehung ist.

Wir zeigen jetzt das für jedes Spiel G und P-Positionsspiel A, A+G  G. Durch die Definition von  müssen wir zeigen, dass G+H in derselben Ergebnis-Klasse wie A+G+H für alle Spiele H ist.

Wenn G+H P-Position ist, dann hat der vorherige Spieler eine Gewinnen-Strategie in A+G+H: Zu jeder Bewegung in G+H antwortet er gemäß seiner gewinnenden Strategie in G+H, und zu jeder Bewegung in ihm erwidert mit seiner gewinnenden Strategie dort. Wenn G+H N-Position ist, dann macht der folgende Spieler in A+G+H eine Gewinnen-Bewegung in G+H, und kehrt dann zur Reaktion seinem Gegner in der näher beschriebenen Art und Weise oben zurück.

Außerdem ist G+G P-Position für jedes Spiel G. Für jede in einer Kopie von G gemachte Bewegung kann der vorherige Spieler mit derselben Bewegung in der anderen Kopie erwidern, was bedeutet, dass er immer die letzte Bewegung macht.

Jetzt können wir das Lemma beweisen.

Wenn G  G' dann G+G' ist derselben Ergebnis-Klasse wie G+G, der P-Position ist.

Andererseits, wenn G+G' ist P-Position dann, da G+G auch P-Position, G  G + ist (G+G')  (G+G) +G'  G' so G 

Beweis

Wir beweisen den Lehrsatz durch die Strukturinduktion auf dem Satz, der das Spiel vertritt.

Denken Sie ein Spiel. Durch die Induktionsvoraussetzung sind alle Optionen zu nimbers gleichwertig, sagen. Wir werden zeigen, dass, wo der mex der Zahlen ist, der die kleinste einigen nicht gleiche natürliche Zahl ist.

Lassen. Das erste Ding, das wir bemerken müssen, ist das. In Betracht ziehen. Wenn der erste Spieler eine Bewegung darin macht, dann kann sich der zweite Spieler zur Entsprechung darin bewegen. Sich danach ist das Spiel eine P-Position (durch das Lemma), da es die Summe von einer Auswahl dessen ist und ein nim gleichwertig zu dieser Auswahl anhäufen. Deshalb, ist eine P-Position, und durch eine andere Anwendung unseres Lemmas.

So, jetzt, durch unser Lemma, müssen wir zeigen, dass das eine P-Position ist. Wir tun so, indem wir eine ausführliche Strategie für den zweiten Spieler in der Entsprechung geben.

Nehmen Sie an, dass sich der erste Spieler im Bestandteil zur Auswahl wo bewegt

Nehmen Sie stattdessen an, dass sich der erste Spieler im Bestandteil zur Auswahl bewegt. Wenn

Deshalb, ist eine P-Position, und ist folglich so. Durch unser Lemma, wie gewünscht.

Entwicklung

Der Sprague-Grundy Lehrsatz ist ins Feld der kombinatorischen Spieltheorie, namentlich von E. R. Berlekamp, John Horton Conway und anderen entwickelt worden. Das Feld wird in den Büchern präsentiert, Wege für Ihre Mathematischen Spiele und Auf Zahlen und Spielen Gewinnend.

Siehe auch

• Klasse-Theorie
• Quotient von Indistinguishability
• Nachgedruckt, 1964, 27: 9-11.

Links

• Das Spiel von Grundy an der Knoten-Kürzung
• Leicht lesbare, einleitende Rechnung von der UCLA Matheabteilung
• Das Spiel von Nim an sputsoft.com