Nimber - Nimber

In der Mathematik werden die Zahlen , auch Grundy-Zahlen genannt , in die kombinatorische Spieltheorie eingeführt , wo sie als die Werte von Haufen im Spiel Nim definiert werden . Die Ziffern sind die Ordnungszahlen, die mit Ziffernaddition und Ziffernmultiplikation ausgestattet sind , die sich von der Ordnungsaddition und der Ordnungsmultiplikation unterscheiden .

Aufgrund des Satzes von Sprague-Grundy, der besagt, dass jedes unparteiische Spiel einem Nim-Heap einer bestimmten Größe entspricht, entstehen Zahlen in einer viel größeren Klasse von unparteiischen Spielen. Sie können auch in Partisanenspielen wie Domineering auftreten .

Zahlen haben die Eigenschaft, dass ihre Optionen Links und Rechts identisch sind, einem bestimmten Schema folgend, und dass sie ihre eigenen Negative sind, so dass eine positive Ordinalzahl zu einer anderen positiven Ordinalzahl hinzugefügt werden kann, indem man die Zahlenaddition verwendet , um eine Ordinalzahl mit einem niedrigeren Wert zu finden. Die minimal ausschließende Operation wird auf Nummernsätze angewendet.

Verwendet

Nim

Nim ist ein Spiel, in dem zwei Spieler abwechselnd Objekte von verschiedenen Haufen entfernen. Da die Züge nur von der Position und nicht davon abhängen, welcher der beiden Spieler sich gerade bewegt, und bei denen die Auszahlungen symmetrisch sind, ist Nim ein unparteiisches Spiel. In jeder Runde muss ein Spieler mindestens einen Gegenstand entfernen und kann beliebig viele Gegenstände entfernen, vorausgesetzt, sie stammen alle vom gleichen Haufen. Das Ziel des Spiels ist es, der Spieler zu sein, der das letzte Objekt entfernt. Unter Verwendung der Nimber-Addition kann jeder Heap summiert werden, um einen Nim-Wert für den Heap zu ergeben. Da alle Haufen zusammen mit Nim-Addition summiert werden können, kann man außerdem die Anzahl des Spiels als Ganzes berechnen. Die Gewinnstrategie dieses Spiels besteht darin, die kumulative Zahl des Spiels für den gegnerischen Zug auf 0 zu zwingen.

Stopfen

Cram ist ein Spiel, das oft auf einem rechteckigen Brett gespielt wird, bei dem die Spieler abwechselnd Dominosteine ​​​​horizontal oder vertikal platzieren, bis keine Dominosteine ​​​​mehr platziert werden können. Der erste Spieler, der keinen Zug machen kann, verliert. Da die möglichen Züge für beide Spieler gleich sind, ist es ein unparteiisches Spiel und kann einen Zahlenwert haben. Wenn jede Zeile und Spalte als Haufen betrachtet wird, ist der Wert des Spiels die Summe aller Zeilen und Spalten unter Verwendung der Zahlenaddition. Zum Beispiel hat jedes 2xn-Board eine Nummer von 0 für alle geraden n und eine Nummer von 1 für alle ungeraden n.

Northcotts Spiel

Ein Spiel, bei dem Spielsteine ​​für jeden Spieler entlang einer Spalte mit einer endlichen Anzahl von Feldern platziert werden. In jeder Runde muss jeder Spieler den Stein in der Spalte nach oben oder unten bewegen, darf jedoch nicht am Stein des anderen Spielers vorbeiziehen. Mehrere Spalten werden zusammen gestapelt, um die Komplexität zu erhöhen. Der Spieler, der keine Züge mehr machen kann, verliert. Im Gegensatz zu vielen anderen Nimber-Spielen entspricht die Anzahl der Leerzeichen zwischen den beiden Spielsteinen in jeder Reihe der Größe der Nim-Haufen. Wenn Ihr Gegner die Anzahl der Felder zwischen zwei Spielsteinen erhöht, verringern Sie sie einfach beim nächsten Zug. Andernfalls spielen Sie das Spiel Nim und machen die Nim-Summe der Anzahl der Felder zwischen den Spielsteinen in jeder Reihe 0.

Hackenbusch

Hackenbush ist ein Spiel, das vom Mathematiker John Horton Conway erfunden wurde . Es kann auf jeder Konfiguration von farbigen Liniensegmenten gespielt werden, die durch ihre Endpunkte miteinander und mit einer "Masse"-Linie verbunden sind. Die Spieler entfernen abwechselnd Liniensegmente. Eine unparteiische Spielversion, also ein Spiel, das unter Verwendung von Zahlen analysiert werden kann, kann gefunden werden, indem die Unterscheidung von den Linien entfernt wird, wodurch es jedem Spieler ermöglicht wird, jeden Zweig abzuschneiden. Alle Segmente, die auf das neu entfernte Segment angewiesen sind, um eine Verbindung mit der Masseleitung herzustellen, werden ebenfalls entfernt. Auf diese Weise kann jede Verbindung zur Erde als Nim-Haufen mit einem Nimber-Wert betrachtet werden. Darüber hinaus können auch alle separaten Verbindungen zur Masseleitung für eine Zahl des Spielzustands summiert werden.

Zusatz

Die Nimber-Addition (auch als Nim-Addition bekannt ) kann verwendet werden, um die Größe eines einzelnen Nim-Heaps zu berechnen, der einer Sammlung von Nim-Heaps entspricht. Es ist rekursiv definiert durch

α ⊕ β = mex({ α ′ ⊕ β  : α' < α } ∪ { α ⊕ β ′ : β ′ < β }) ,

wobei das minimale ausschließende mex( S ) einer Menge S von Ordinalzahlen definiert ist als die kleinste Ordinalzahl, die kein Element von S ist .

Für endliche Ordinalzahlen, die NIM-Summe ist leicht auf einem Computer ausgewertet , indem die Einnahme bitweisen Exklusiv - ODER (XOR, indem bezeichnet ⊕ ) der entsprechenden Zahlen. Zum Beispiel kann die Nim-Summe von 7 und 14 gefunden werden, indem man 7 als 111 und 14 als 1110 schreibt; die Einerstelle addiert sich zu 1; die Zweierstelle addiert sich zu 2, die wir durch 0 ersetzen; die Viererstelle addiert sich zu 2, die wir durch 0 ersetzen; die Achterstelle addiert sich zu 1. Die Nim-Summe wird also binär als 1001 oder dezimal als 9 geschrieben.

Diese Additionseigenschaft folgt aus der Tatsache, dass sowohl mex als auch XOR eine Gewinnstrategie für Nim ergeben und es nur eine solche Strategie geben kann; oder es kann direkt durch Induktion gezeigt werden: Seien α und β zwei endliche Ordinalzahlen, und nehmen Sie an, dass die Nim-Summe aller Paare, von denen eines reduziert ist, bereits definiert ist. Die einzige Zahl , deren XOR mit α IS α & xoplus; β IS β , und umgekehrt; somit ist α ⊕ β ausgeschlossen. Andererseits muss für jede Ordinalzahl γ < α ⊕ β die XOR-Verknüpfung ξ ≔ α ⊕ β ⊕ γ mit allen α , β und γ zu einer Reduktion für eine davon führen (da die führende 1 in ξ in mindestens einer der drei); da ξ ⊕ γ = α ⊕ β > γ , gilt α > ξ ⊕ α = β ⊕ γ oder β > ξ ⊕ β = α ⊕ γ ; somit γ ist enthalten , wie ( & bgr; & xoplus; γ ) & xoplus; & bgr; oder als α ⊕ (α ⊕ γ) und damit & agr; & xoplus; & bgr; ist die minimale ordinal ausgeschlossen.

Multiplikation

Nimber-Multiplikation ( Nim-Multiplikation ) ist rekursiv definiert durch

α β = mex ({ α ' β & xoplus; α β ' & xoplus; α‘ β ': α ' < α , β '< β }) .

Abgesehen von der Tatsache, dass Zahlen eine echte Klasse und keine Menge bilden, bestimmt die Zahlenklasse einen algebraisch abgeschlossenen Körper des Merkmals 2. Die additive Zahlenidentität ist die Ordinalzahl 0 und die Zahlenmultiplikatoridentität ist die Ordinalzahl 1. Gemäß Merkmal 2, die nimber additive inverse der Ordinalzahl α IST α selbst. Die multiplikative Nimber-Inverse der von Null verschiedenen Ordinalzahl α ist gegeben durch 1/ α = mex( S ) , wobei S die kleinste Menge von Ordinalzahlen (Zahlen) mit ist

1. 0 ist ein Element von S ;
2. wenn 0 < α ′ < α und β ′ ein Element von S ist , dann ist [1 + (α′ − α) β′] / α′ auch ein Element von S .

Für alle natürlichen Zahlen n bildet die Menge der Zahlen kleiner als 2 ^{2 n} das Galois-Feld GF(2 ^{2 n} ) der Ordnung  2 ^{2 n} .

Dies impliziert insbesondere, dass die Menge der endlichen Zahlen isomorph zum direkten Limes ist, da n → ∞ der Körper GF(2 ^{2 n} ) ist . Dieser Teilkörper ist nicht algebraisch abgeschlossen, da kein anderer Körper GF(2 ^k ) (also mit k keine Potenz von 2) in einem dieser Felder enthalten ist, und daher nicht in ihrem direkten Grenzwert; zum Beispiel hat das Polynom x ³ + x + 1 , das eine Wurzel in GF(2 ³ ) hat , keine Wurzel in der Menge endlicher Zahlen.

Genau wie bei der Zahlenaddition gibt es eine Möglichkeit, das Zahlenprodukt endlicher Ordinalzahlen zu berechnen. Dies wird durch die Regeln bestimmt, die

1. Das Zahlenprodukt einer Fermat-2-Potenz (Zahlen der Form 2 ^{2 n} ) mit einer kleineren Zahl ist gleich ihrem gewöhnlichen Produkt;
2. Das Zahlenquadrat einer Fermat-2-Potenz x ist gleich 3 x /2, wie es bei der gewöhnlichen Multiplikation natürlicher Zahlen berechnet wird.

Der kleinste algebraisch abgeschlossene Zahlenkörper ist die Menge der Zahlen kleiner als die Ordinalzahl ω ^{ω ω} , wobei ω die kleinste unendliche Ordinalzahl ist. Daraus folgt , dass als nimber, & ohgr; ^{& ohgr; & ohgr;} IS transzendentalen über das Feld.

Additions- und Multiplikationstabellen

Die folgenden Tabellen zeigen Addition und Multiplikation unter den ersten 16 Ziffern.
Diese Teilmenge ist unter beiden Operationen abgeschlossen, da 16 die Form  2 ^{2 n hat} . (Wenn Sie einfache Texttabellen bevorzugen, sind sie hier .)

Nimber-Addition (Sequenz A003987 im OEIS )
Dies ist auch die Cayley-Tabelle von Z ₂ ⁴ – oder die Tabelle der bitweisen XOR- Operationen.
Die kleinen Matrizen zeigen die einzelnen Stellen der Binärzahlen.

Nimber-Multiplikation (Sequenz A051775 im OEIS )
Die von Null verschiedenen Elemente bilden die Cayley-Tabelle von Z ₁₅ .
Die kleinen Matrizen sind permutierte binäre Walsh-Matrizen .

Nimber-Multiplikation von Zweierpotenzen (Sequenz A223541 im OEIS ) Die
Berechnung der Nim-Produkte von Zweierpotenzen ist ein entscheidender Punkt im rekursiven Algorithmus der Nimber-Multiplikation.

Siehe auch

• Surreale Zahl

Anmerkungen

Verweise