Nim
Nim este un joc de matematică pentru doi jucători.
Reguli
Începe cu o serie de grămezi care conțin un anumit număr de elemente (numărul grămezilor și elementele fiecărei grămezi sunt convenite după bunul plac între jucători la începutul jocului). Jucătorii elimină pe rând orice număr de elemente din orice grămadă, de la unul la toate. Câștigătorul este cel care elimină ultimul element prezent pe terenul competiției. Nu este posibil să treci (sări peste mișcare).
Există, de asemenea, o variantă numită Marienbad, din filmul Anul trecut în Marienbad de Alain Resnais, în care a fost interpretat de protagonist. În această variantă pierde cine elimină ultimul element.
Strategie
Nimul a devenit destul de celebru deoarece are o strategie simplă de câștig (are clasa de complexitate L ), ușor de utilizat ca exemplu în teoria jocurilor.
Strategia se bazează pe calculul binar și tocmai pe o anumită adăugare prin cifre a reprezentării binare a numărului de elemente din stive: se realizează ca o sumă normală (dar în sistemul binar, unde de exemplu 10 2 + 11 2 = 101 2 ) dar omiterea reportărilor. Acest tip de sumă, având în vedere numerele cifră cu cifră, corespunde disjuncției exclusive sau adunării în câmpul finit . În teoria jocurilor, datorită utilizării sale în această strategie, este numită și nim sum .
Exemplu
1010011 + 0100110 _______ = 1110101
Strategia jocului se bazează pe distincția dintre poziții (sau configurații) sigure și nesigure . Se spune că o configurație este sigură dacă suma nim a reprezentărilor binare ale elementelor stivelor dă 0; altfel se spune că este nesigur. Strategia câștigătoare constă în lăsarea adversarului, la fiecare mișcare, a unei configurații sigure. Este întotdeauna posibil să se atingă o poziție sigură pornind de la una nesigură (și invers), în timp ce este imposibil să se obțină o poziție sigură pornind de la o configurație sigură.
Exemple
Poziţie
Stiva 1: 3 elemente ooo Stiva 2: 4 elemente oooo Stiva 3: 5 elemente ooooo 3 10 = 011 2 4 10 = 100 2 5 10 = 101 2 0 1 1 + 1 0 0 + 1 0 1 ------- 0 1 0
Suma nu dă zero, deci poziția este nesigură.
Mutare
O mișcare câștigătoare trebuie să aducă suma nim la zero. Acest lucru se poate face prin modificarea primului addend pentru a „anula” 1 pe locul al doilea. În practică, aducem stiva 1 de la 3 elemente la 1:
Stiva 1: 1 element o Stiva 2: 4 elemente oooo Stiva 3: 5 elemente ooooo 1 10 = 001 2 4 10 = 100 2 5 10 = 101 2 0 0 1 + 1 0 0 + 1 0 1 -------- 0 0 0
Locația este acum sigură. Adversarul, acum, nu se va mai putea mișca în nici un fel fără să alerge într-o poziție nesigură.
Bibliografie
- Martin Gardner , Puzzle și jocuri matematice , BUR 2001.
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe nim
linkuri externe
- ( EN ) Nim , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
