Nimber

In matematik , içinde kombinatoryal oyun teorisi , nimbers olarak tanımlanan belirli oyunlar vardır tek kazık Nim oyunların eşleşmelerin muhtemelen sonsuz sayı ile.

Daha kesin olarak, sıra numarasına karşılık gelen sayı işareti , genellikle * olarak belirtilir , Nim oyununun bir dizi kibrit ile eşleşmelerinin yığını olarak tanımlanır . Bir nimber ayrıca doğrudan bu sayıda eşleşmeye de başvurabilir. α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}α{\ displaystyle \ alpha}

Nimbers teorisinin özellikle müdahale tarafsız oyunlara  : göre, gerçekten de Sprague-Grundy teoremi , herhangi tarafsız oyun belli eşdeğerdir nimber .

Nim oyunu bitti

Kaybedenin artık oynayamayacak kişi olduğu sonlu bir Nim oyunu durumunda, bu oyunun her pozisyonuna Grundy numarası veya nimber adı verilen ve aşağıdaki gibi yinelemeli olarak tanımlanan bir sayı atarız:

• Son konumun sayısı 0'a eşittir.
• Belirli bir pozisyonun sayacı, verilen pozisyonu hemen takip eden pozisyonların nimberleri listesinde görünmeyen en küçük pozitif veya sıfır tamsayıdır.

Önemsiz tek kazık Nim oyununda, tek bir n kibrit yığını n'in kendisidir.

Nimberleri 0 değerinde olan pozisyonlar, elde edilmesi gereken kazanan pozisyonlar, diğerleri ise pozisyon kaybediyor. Nitekim, sıfır sıfıra sahip bir pozisyona ulaşan oyuncu, rakibinin, sıfır olmayan bir sümüklü pozisyona ulaştığını görecek ve bu pozisyon ne olursa olsun, kendisi de oynayacağı bir vuruşa sahip olacak ve bu da onu bir pozisyona geri getirebilecektir. sıfır olmayan nimber nimber null. Bu nedenle, rakibi engellenene kadar bir sıfır noktadan diğerine geçebilir.

Bu durum, oyunun konumu ne olursa olsun, oyun bitmeden önce yalnızca sınırlı sayıda hamle olması koşuluyla, sonsuz oyuna genelleştirilir. Bununla birlikte, her pozisyonun sonsuz sayıda halefi olabilir. Bu durumda, parmak uçları sıra sayıları ile gösterilen sonsuz değerler alabilir . Bu parmak uçları, aşağıda açıklanan ilginç özelliklere sahip olabilir.

Nimber'lar üzerinde operasyon

Endows nimbers ve çarpma işlemleri hakkında tanımlamak mümkündür sınıfı , bir ile nimbers arasında cebirsel olarak kapalı değişmeli alan yapısının bir karakteristik Bu teorik yapı 1976 de tarif edilmiştir 2. Numaraları ve Oyunlarım'da göre, John Horton Conway .

Kümeler için genellikle cebirsel bir yapıdan bahsettiğimize dikkat edilmelidir . Bununla birlikte, sıralı sayılar gibi hokkabazlar bir küme değil , kendi başına bir sınıf oluşturur . Bu nedenle, yanlış bir ifade olacak olan sersemleticiler kümesinin yapısını değil, sersemleticiler sınıfının yapısını ele alıyoruz.

Ekleme işlemi

Nimbers üzerindeki işlemlerin tanımı ilk Güneybatı işlevini adlandırılan gerektirir m inimum ex clu. Bir sıra sıra dizisinin mex'i, bu kümeye ait olmayan en küçük sıra olarak tanımlanır. Örneğin :

• Mex (1, 2) = 0
• Mex (0, 1, 5, 6) = 2
• Mex (0, 1, 2, 3, ..., ω, ω + 5) = ω + 1

Bir grup dolandırıcı için tam olarak aynı mex tanımını kullanıyoruz, yani bir sersemletme setinin mex'i bu sete ait olmayan en küçük nimberdir. Bir Nim oyunu durumunda, belirli bir pozisyonun nimberinin hesaplanması, tam olarak hemen arka pozisyonların tüm nimberlerinin meksini almaktan ibarettir.

İki nimbers ekleme işlemi ve aşağıdaki şekilde tanımlanır: α{\ displaystyle \ alpha}β{\ displaystyle \ beta}

α⊕β=Meksika⁡({α′⊕β:α′<α}∪{α⊕β′:β′<β}),{\ displaystyle \ alpha \ oplus \ beta = \ operatorname {mex} (\ {\, \ alpha '\ oplus \ beta: \ alpha' <\ alpha \, \} \ cup \ {\, \ alpha \ oplus \ beta ': \ beta' <\ beta \, \}),}

Göre Sprague-Grundy teoremi , bu işlem pozisyonunun nimber hesaplayan iki kazık Nim ait oyunda (veya Marienbad oyun sırasıyla sahip) ve onun takdirine iki kazık birini seçerek her oyuncu çekilme, nesneler. Sayısını istediği nesneler. (α,β){\ displaystyle (\ alpha, \ beta)}α{\ displaystyle \ alpha}β{\ displaystyle \ beta}

Sonlu bir durumda, bu ekleme aynıdır dışlayan ya da içinde ikili . Yazılı olarak ve de ikili , bu carry-over dikkate almadan iki sayıyı ilave etmek yeterlidir. α{\ displaystyle \ alpha}β{\ displaystyle \ beta}

Abelian grup yapısı

Süngerler üzerinde tanımlanan toplama işlemi aşağıdaki dikkat çekici özelliklere sahiptir:

• nimber 0 nötr bir elementtir: α⊕0=α{\ displaystyle \ alpha \ oplus 0 = \ alpha}
• değişme: α⊕β=β⊕α{\ displaystyle \ alpha \ oplus \ beta = \ beta \ oplus \ alpha}
• birliktelik: (α⊕β)⊕γ=α⊕(β⊕γ){\ displaystyle (\ alpha \ oplus \ beta) \ oplus \ gamma = \ alpha \ oplus (\ beta \ oplus \ gamma)}
• Her nimber'ın bir zıttı (kendisi) vardır: ve bu nedenleα⊕α=0{\ displaystyle \ alpha \ oplus \ alpha = 0}-α=α{\ displaystyle - \ alpha = \ alpha}

Bu özellikler, nimber sınıfına değişmeli bir grup yapısı kazandırır . Son özellik, iki eşit desteden oluşan iki kümeli bir Nim oyununun pozisyonunun kazanan bir pozisyon olduğu gerçeğini ifade eder: böyle bir konuma ulaşan ilk oyuncu, daha sonra rakibinin simetrik olarak oynayarak her zaman iki eşit yığın tutana kadar oynar. hiç nesne kalmadı.

Çarpma işlemi

İki dolandırıcının çarpımı şu şekilde tanımlanır:

• α⊗β=Meksika⁡({(α′⊗β)⊕(α⊗β′)⊕(α′⊗β′):α′<α,β′<β}),{\ displaystyle \ alpha \ otimes \ beta = \ operatorname {mex} (\ {\, (\ alpha '\ otimes \ beta) \ oplus (\ alpha \ otimes \ beta') \ oplus (\ alpha '\ otimes \ beta '): \ alpha' <\ alpha, \ beta '<\ beta \, \}),}

Bu ürün, aşağıdaki gibi tanımlanan iki setin çarpımının konumlarının parmaklarını hesaplamak için kullanılır : P×Q{\ displaystyle P \ times Q}

• Ürün setinin bir pozisyon olan elemanları (bir dizi , bir , b ) bir konum arasında oluşan a grubu P ve bir konum B grubu S.
• Ürün kümesinin ilk konum, elemanları (bir dizi , bir , b ) bir oluşturulmaktadır , ilk pozisyon a grubu P ve bir başlangıç konumu b grubu, Q nun
• Üretilen kümesinin son pozisyonu, elemanları (bir dizi , bir , b ) bir oluşturulmaktadır son konum a grubu P veya bir son pozisyonu b grubu S.
• Başladığımız konumun bir öğesini ( a , b ) seçip onu üçlü ( a ' , b ), ( a , b' ), ( a ' , b' ) ile değiştirerek bir konumdan diğerine geçiyoruz. burada, bir ' ulaşılabilir P bir pozisyon , bir ve B' ulaşılabilir Q'nun bir konum b .

Ürün aşağıdaki özelliklere sahiptir:

• nimber 1 nötr bir elementtir: α⊗1=α{\ displaystyle \ alpha \ otimes 1 = \ alpha}
• değişme: α⊗β=β⊗α{\ displaystyle \ alpha \ otimes \ beta = \ beta \ otimes \ alpha}
• birliktelik: (α⊗β)⊗γ=α⊗(β⊗γ){\ Displaystyle (\ alfa \ otimes \ beta) \ otimes \ gama = \ alfa \ otimes (\ beta \ otimes \ gama)}
• toplamaya göre dağılım: (α⊕β)⊗γ=(α⊗γ)⊕(β⊗γ){\ Displaystyle (\ alpha \ oplus \ beta) \ otimes \ gamma = (\ alpha \ otimes \ gamma) \ oplus (\ beta \ otimes \ gamma)}
• Sıfır olmayan her nimber'ın bir tersi vardır

Vücut yapısı

Ekleme ve ürün, değişmeli bir alan yapısına sahip nimber sınıfına sağlar .

En şaşırtıcı özellik, her nimberin bir tersi olmasıdır. Bu, tersi tümevarımsal olarak yapılandırmaya izin veren açık bir formülle gösterilir. Tümevarımla bir S kümesi tanımlarız:

• 0∈S{\ displaystyle 0 \ S’de}
• o zaman her şey için elimizde:β′∈S{\ displaystyle \ beta '\ S}α′<α{\ displaystyle \ alpha '<\ alpha}1⊕((α′⊕α)⊗β′)α′∈S{\ displaystyle {\ frac {1 \ oplus ((\ alpha '\ oplus \ alpha) \ otimes \ beta')} {\ alpha '}} \ S içinde}

Daha sonra bunun doğrulandığını gösterebiliriz , yani . β=Meksika⁡(S){\ displaystyle \ beta = \ operatöradı {mex} (S)}α⊗β=1{\ displaystyle \ alpha \ otimes \ beta = 1}β=1α{\ displaystyle \ beta = {\ frac {1} {\ alpha}}}

Olağanüstü alt gövdeler

Ayırıcıların bazı alt kümeleri, toplama ve çarpma işlemleri için kararlıdır. Verilen n> 0 için:

• 0 ile arasındaki işaretler kümesi , ekleme işlemi için kararlıdır2değil-1{\ displaystyle 2 ^ {n} -1}
• 0'dan sıfırlama kümesi çarpma işlemi için kararlıdır22değil-1{\ displaystyle 2 ^ {2 ^ {n}} - 1}

0 ila nimbers grubu için bu, aşağıdaki a, sonlu alan ile farklı elemanlar ve bu nedenle izomorfik . 22değil-1{\ displaystyle 2 ^ {2 ^ {n}} - 1}22değil{\ displaystyle 2 ^ {2 ^ {n}}}F22değil{\ displaystyle F_ {2 ^ {2 ^ {n}}}}

Sonlu alt gövde F 16 örneği

Toplama ve çarpma işlemlerini göstermek için, 0 ile 15 arasında ayraçların toplanması ve çarpımının sonucunu gösteren aşağıdaki tabloları verebiliriz. Bu işlemler için 0'dan 15'e kadar çevirme seti kapalıdır, yani sonucun 0 ile 15 arasında bir sayı olduğunu söylemek için. Böylece sonlu F 16 alanına izomorfik bir yapı elde ederiz .

Nimbers toplama tablosu + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Nimbers çarpım tablosu × 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2 0 2 3 1 8 10 11 9 12 14 15 13 4 6 7 5 3 0 3 1 2 12 15 13 14 4 7 5 6 8 11 9 10 4 0 4 8 12 6 2 14 10 11 15 3 7 13 9 5 1 5 0 5 10 15 2 7 8 13 3 6 9 12 1 4 11 14 6 0 6 11 13 14 8 5 3 7 1 12 10 9 15 2 4 7 0 7 9 14 10 13 3 4 15 8 6 1 5 2 12 11 8 0 8 12 4 11 3 7 15 13 5 1 9 6 14 10 2 9 0 9 14 7 15 6 1 8 5 12 11 2 10 3 4 13 10 0 10 15 5 3 9 12 6 1 11 14 4 2 8 13 7 11 0 11 13 6 7 12 10 1 9 2 4 15 14 5 3 8 12 0 12 4 8 13 1 9 5 6 10 2 14 11 7 15 3 13 0 13 6 11 9 4 15 2 14 3 8 5 7 10 1 12 14 0 14 7 9 5 11 2 12 10 4 13 3 15 1 8 6 15 0 15 5 10 1 14 4 11 2 13 7 8 3 12 6 9

Referanslar

1. JH Conway On Sayılar ve Oyunlar 2. baskı, AK Peters (2000), s.  50 - 63
2. HW Lenstra, Nim çarpımı , IHES, Bures-sur-Yvette (1978)

• (in) Elwyn Berlekamp John Conway ve Richard K. Guy, senin Matematik Oynatmaları için Yolları Winning 2001 den -2004 için, AK Peters Ltd., 2 inci  ed. ( ISBN  978-1-56881-130-7 , 1-56881-142-X ve 1-56881-143-8 )