Nimber
W matematyce nimbery , zwane też liczbami Grundy'ego , zostały wprowadzone w kombinatorycznej teorii gier , gdzie określa się je jako wartości stosów w grze Nim . Nimbery to liczby porządkowe wyposażone w dodawanie nimber i mnożenie nimber , które różnią się od dodawania porządkowego i mnożenia porządkowego .
Ze względu na twierdzenie Sprague-Grundy'ego, które mówi, że każda bezstronna gra jest równoważna stercie Nim o określonej wielkości, nimbery powstają w znacznie większej klasie bezstronnych gier. Mogą również wystąpić w grach partyzanckich, takich jak Domineering .
Nimbery mają tę cechę, że ich opcje Lewa i Prawa są identyczne, zgodnie z pewnym schematem, i że są swoimi własnymi negatywami, tak że dodatnia liczba porządkowa może być dodana do innej dodatniej liczby porządkowej za pomocą dodatku nimber, aby znaleźć liczbę porządkową o niższej wartości. Minimalna wykluczająca jest stosowana do zestawów nimberów.
Używa
Nim
Nim to gra, w której dwóch graczy na zmianę usuwa przedmioty z różnych stosów. Ponieważ ruchy zależą tylko od pozycji, a nie od tego, który z dwóch graczy aktualnie się porusza, i gdzie wypłaty są symetryczne, Nim jest grą bezstronną. W każdej turze gracz musi usunąć co najmniej jeden przedmiot i może usunąć dowolną liczbę przedmiotów, pod warunkiem, że wszystkie pochodzą z tego samego stosu. Celem gry jest bycie graczem, który usunie ostatni przedmiot. Nimber sterty to po prostu liczba obiektów w tej stercie. Za pomocą dodatku nim można obliczyć nimber gry jako całości. Zwycięska strategia polega na wymuszeniu nimberu gry na 0 w turze przeciwnika.
Dopchać
Cram to gra często rozgrywana na prostokątnej planszy, w której gracze na zmianę układają kostki domina poziomo lub pionowo, aż nie będzie można umieścić więcej kostek domina. Pierwszy gracz, który nie może wykonać ruchu, przegrywa. Ponieważ możliwe ruchy dla obu graczy są takie same, jest to gra bezstronna i może mieć niewielką wartość. Na przykład każda plansza o parzystym rozmiarze o parzystym rozmiarze będzie miała nimber równy 0. Każda plansza o parzystym i nieparzystym rozmiarze będzie miała nimber niezerowy. Każda 2× n będzie miała nimber równy 0 dla wszystkich parzystych n i nimber równy 1 dla wszystkich nieparzystych n .
Gra Northcotta
Gra, w której kołki dla każdego gracza są umieszczane wzdłuż kolumny ze skończoną liczbą pól. W każdej turze każdy gracz musi przesunąć pionek w górę lub w dół kolumny, ale nie może przekroczyć piona drugiego gracza. Kilka kolumn jest ułożonych razem, aby zwiększyć złożoność. Gracz, który nie może już wykonywać żadnych ruchów, przegrywa. W przeciwieństwie do wielu innych gier związanych z nimberem, liczba pól między dwoma żetonami w każdym rzędzie odpowiada rozmiarom stosów Nimber. Jeśli twój przeciwnik zwiększy liczbę pól między dwoma żetonami, po prostu zmniejsz ją w następnym ruchu. W przeciwnym razie zagraj w grę Nim i spraw, aby suma Nim liczby miejsc między żetonami w każdym rzędzie wynosiła 0.
Hackenbush
Hackenbush to gra wymyślona przez matematyka Johna Hortona Conwaya . Można w nią grać na dowolnej konfiguracji kolorowych odcinków linii połączone ze sobą punktami końcowymi i linią „uziemienia”. Gracze na zmianę usuwają segmenty linii. Bezstronną wersję gry, a tym samym grę, którą można analizować za pomocą nimberów, można znaleźć, usuwając rozróżnienie z linii, umożliwiając każdemu graczowi cięcie dowolnej gałęzi. Wszystkie segmenty zależne od nowo usuniętego segmentu w celu połączenia z linią uziemienia również zostaną usunięte. W ten sposób każde połączenie z ziemią można uznać za stertę nimber z wartością nimber. Dodatkowo wszystkie oddzielne połączenia z linią naziemną można również zsumować dla jednego stanu gry.
Dodatek
Dodatek nimber (znany również jako nim-addition ) może być użyty do obliczenia rozmiaru pojedynczej sterty nim równoważnej zbiorowi stert nim. Jest zdefiniowany rekurencyjnie przez
- α ⊕ β = mex ({ α ′ ⊕ β : α' < α } ∪ { α ⊕ β ′ : β ′ < β }) ,
gdzie minimalna wykluczająca mex( S ) zbioru S liczb porządkowych jest zdefiniowana jako najmniejsza liczba porządkowa, która nie jest elementem S .
W przypadku skończonych liczb porządkowych sumę nim można łatwo obliczyć na komputerze, biorąc wyłączność bitową lub (XOR, oznaczony przez ⊕ ) odpowiednich liczb. Na przykład sumę nim 7 i 14 można znaleźć, zapisując 7 jako 111, a 14 jako 1110; jedno miejsce dodaje do 1; miejsce dwójek dodaje 2, które zastępujemy 0; miejsce czwórek sumuje się do 2, które zamieniamy na 0; miejsce ósemki dodaje się do 1. Tak więc suma nim jest zapisywana binarnie jako 1001 lub dziesiętnie jako 9.
Ta właściwość dodawania wynika z faktu, że zarówno mex, jak i XOR dają Nim zwycięską strategię, a taka strategia może być tylko jedna; lub można to wykazać bezpośrednio przez indukcję: niech α i β będą dwoma skończonymi liczbami porządkowymi i załóżmy, że suma nim wszystkich par z jedną z nich zredukowaną jest już zdefiniowana. Jedyną liczbą, której XOR z α jest α ⊕ β , jest β i odwrotnie; zatem α ⊕ β jest wykluczone. Z drugiej strony dla dowolnej liczby porządkowej γ < α ⊕ β , XORowanie ξ ≔ α ⊕ β ⊕ γ ze wszystkimi α , β i γ musi prowadzić do redukcji dla jednego z nich (ponieważ wiodąca 1 w ξ musi być obecna przynajmniej w jednym z trzech); skoro ξ ⊕ γ = α ⊕ β > γ , to musimy mieć α > ξ ⊕ α = β ⊕ γ lub β > ξ ⊕ β = α ⊕ γ ; zatem γ jest zawarte jako ( β ⊕ γ ) ⊕ β lub jako α ⊕ (α ⊕ γ) , a zatem α ⊕ β jest minimalną wykluczoną liczbą porządkową.
Mnożenie
Mnożenie nimber ( nim-multiplication ) jest definiowane rekurencyjnie przez
- α β = mex ({ α ′ β ⊕ α β ′ ⊕ α' β ′: α ′ < α , β ′ < β }) .
Poza tym, że nimbery tworzą klasę właściwą , a nie zbiór, klasa nimberów określa algebraicznie domknięte pole o charakterystyce 2. Tożsamość addytywna nimber to liczba porządkowa 0, a tożsamość multiplikatywna nimber to liczba porządkowa 1. Zgodnie z cechą charakterystyczną jest 2, odwrotnością dodatku nimber do porządkowej α jest sama α . Multiplikatywna odwrotność nimber niezerowej liczby porządkowej α jest dana przez 1/ α = mex( S ) , gdzie S jest najmniejszym zbiorem liczb porządkowych (nimbers) takim, że
- 0 jest elementem S ;
- jeśli 0 < α ′ < α i β ′ jest elementem S , to [1 + (α′ - α) β′] / α′ jest również elementem S .
Dla wszystkich liczb naturalnych n zbiór nimberów mniejszych od 2 2 n tworzy ciało Galois GF(2 2 n ) rzędu 2 2 n . Dlatego zbiór nimberów skończonych jest izomorficzny z bezpośrednią granicą jako n → ∞ ciał GF(2 2 n ) . To podciało nie jest algebraicznie domknięte, ponieważ nie ma ciała GF(2 k ) z k żadna potęga 2 nie jest zawarta w żadnym z tych pól, a zatem nie w ich bezpośredniej granicy; na przykład wielomian x 3 + x + 1 , który ma pierwiastek w GF(2 3 ) , nie ma pierwiastka w zbiorze skończonych nimberów.
Podobnie jak w przypadku dodawania nimber, istnieje sposób obliczania iloczynu nimber skończonych liczb porządkowych. Decydują o tym przepisy, które
- Iloczyn nimber potęgi Fermata 2 (liczby postaci 2 2 n ) z mniejszą liczbą jest równy ich iloczynowi zwykłemu;
- Kwadrat nimbera Fermata 2-potęgi x jest równy 3 x / 2 , oceniany przy zwykłym mnożeniu liczb naturalnych.
Najmniejszym algebraicznie zamkniętym polem nimberów jest zbiór nimberów mniejszych niż liczba porządkowa ω ω ω , gdzie ω jest najmniejszą nieskończoną liczbą porządkową. Wynika z tego, że jako nimber, ω ω ω jest transcendentalne nad polem.
Tabliczki dodawania i mnożenia
Poniższe tabele przedstawiają dodawanie i mnożenie wśród pierwszych 16 nimberów. Ten podzbiór jest domknięty dla obu operacji, ponieważ 16 ma postać 2 2 n . (Jeśli wolisz proste tabele tekstowe, są to .)
15 Nimbera (sekwencja A051775 w OEIS ) Elementy niezerowe tworzą tablicę Cayleya Z . Małe macierze są permutowanymi binarnymi macierzami Walsha .
Nimber mnożenie potęg dwójki (sekwencja A223541 w OEIS ) Obliczanie nim-iloczynów potęg dwójki jest decydującym punktem w rekurencyjnym algorytmie mnożenia nimber.
Zobacz też
Notatki
- Conway, John Horton (1976). O liczbach i grach . Academic Press Inc. (Londyn) Ltd.
- Lenstra, HW (1978). Mnożenie Nim . Raport IHES/M/78/211. Institut des hautes études scientifiques. hdl : 1887/2125 .
- Schleicher, Dierk; Stoll, Michael (2004). „Wprowadzenie do gier i liczb Conwaya”. arXiv : math.DO/0410026 . który omawia gry, surrealistyczne liczby i nimby.