Home Jocul Explicatii Algoritm Analiza algoritmului Despre NIM - istoria jocului


                    Secretele jocului NIM

Se considera mai multe gramezi, fiecare gramada avand un numar oarecare de monezi. Doi jucatori iau alternativ monezi din ele, fiecare jucator putand lua orice numar de monezi, din orice gramada (insa numai din una). Se considera ca a castigat jucatorul care ia ultima moneda.

Se poate juca cu oricate gramezi, eu am ales doar 5. In fiecare gramada pot fi oricate obiecte (monezi), eu am ales 19 monezi maxim. Obiectele pot si de orice tip, eu am ales monezi.


      NIM este un joc logic, care se poate castiga foarte usor cu ajutorul algebrei booleene. Daca stiti algoritmul si il aplicati corect pe tot parcursul jocului nu veti putea fi invins, insa daca faceti cea mai mica greseala, nu mai aveti nici o sansa de castig..Voi explica algoritmul pe exemplul de mai sus, explicand fiecare mutare pe care trebuie sa o efectuati pentru a castiga (puteti sa verificati algoritmul pe un alt exemplu si sa testati pozitia calculata de dumneavoastra cu ajutorul butonului "Ajutor!").
      In cazul de mai sus, avem pe rand in fiecare gramada: 15, 14, 5, 7 si 15 monezi. Voi construi o matrice, care pe linia i (i intre 1 si 5) va avea numarul de obiecte din gramada i scris in binar. In acest caz matricea va fi urmatoarea:

        Gramada 1 (15 monezi)         0   1   1   1   1
        Gramada 2 (14 monezi)         0   1   1   1   0
        Gramada 3 (  5 monezi)         0   0   1   0   1
        Gramada 4 (  7 monezi)         0   0   1   1   1
        Gramada 5 (15 monezi)         0   1   1   1   1

      Daca se face XOR pe fiecare coloana se poate observa ca pe coloanele 2 si 3 se obtine 1. Ideea algoritmului este sa luam atatea obiecte dintr-o anumita gramada astfel incat efectuand iar XOR pe fiecare coloana sa obtinem 0. In cazul nostru daca inlocuim prima linie cu 0 0 0 1 1 (de fapt nu este nevoie sa inlocuim toata linia ci doar elementele de pe coloanele care dau 1) si facem XOR pe toate coloanele vom obtine 0, deci vom ajunge intr-o pozitie sigura. Atunci cand modificam linia din matrice se modifica si numarul de elemente din matrice...in cazul nostru pe linia 1 ar trebui sa avem 3 elemente, deci trebuie sa apasam pe elementul 4.
      Voi prezenta mai jos toate etapele acestui exemplu:

In gramada 1 au ramas 3 obiecte si dupa cum se poate observa calculatorul a luat 2 obiecte din gramada 4. Matricea binara arata astfel:
        Gramada 1 (  3 monezi)         0   0   0   1   1
        Gramada 2 (14 monezi)         0   1   1   1   0
        Gramada 3 (  5 monezi)         0   0   1   0   1
        Gramada 4 (  5 monezi)         0   0   1   0   1
        Gramada 5 (15 monezi)         0   1   1   1   1

Efectuand XOR-ul se va constata ca pe coloana 4 vom avea 1, deci trebuie sa luam monezi astfel incat sa obtinem 0. Inlocuim prima linie cu 0 0 0 0 1 (luam monezi astfel incat in prima gramada sa ramana 1 obiect).


In gramada 1 a ramas 1 obiect si dupa cum se poate observa calculatorul a luat 3 obiecte din gramada 3. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (14 monezi)         0   1   1   1   0
        Gramada 3 (  2 monezi)         0   0   0   1   0
        Gramada 4 (  5 monezi)         0   0   1   0   1
        Gramada 5 (15 monezi)         0   1   1   1   1

Efectuand XOR-ul se va constata ca pe coloanele 3, 4, 5 vom avea 1. Inlocuim linia 2 cu 0 1 0 0 1 (luam monezi astfel incat in a doua gramada sa ramana 9 obiecte).


In gramada 2 au ramas 9 obiecte si dupa cum se poate observa calculatorul a luat 2 obiecte din gramada 4. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (  9 monezi)         0   1   0   0   1
        Gramada 3 (  2 monezi)         0   0   0   1   0
        Gramada 4 (  3 monezi)         0   0   0   1   1
        Gramada 5 (15 monezi)         0   1   1   1   1

Efectuand XOR-ul se va constata ca pe coloanele 3, 4 vom avea 1. Inlocuim linia 5 cu 0 1 0 0 1 (luam monezi astfel incat in gramada 5 sa ramana 9 obiecte).


In gramada 5 au ramas 9 obiecte si dupa cum se poate observa calculatorul a luat 5 obiecte din gramada 2. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (  4 monezi)         0   0   1   0   0
        Gramada 3 (  2 monezi)         0   0   0   1   0
        Gramada 4 (  3 monezi)         0   0   0   1   1
        Gramada 5 (  9 monezi)         0   1   0   0   1

Efectuand XOR-ul se va constata ca pe coloanele 2, 3, 5 vom avea 1. Inlocuim linia 5 cu 0 0 1 0 0 (luam monezi astfel incat in gramada 5 sa ramana 4 obiecte).


In gramada 5 au ramas 4 obiecte si dupa cum se poate observa calculatorul a luat 2 obiecte din gramada 4. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (  4 monezi)         0   0   1   0   0
        Gramada 3 (  2 monezi)         0   0   0   1   0
        Gramada 4 (  1 monezi)         0   0   0   0   1
        Gramada 5 (  4 monezi)         0   0   1   0   0

Efectuand XOR-ul se va constata ca pe coloana 4 vom avea 1. Inlocuim linia 3 cu 0 0 0 0 0 (luam toate monezile din gramada 3).


In gramada 3 nu mai am nici un obiect si dupa cum se poate observa calculatorul a luat 1 obiect din gramada 2. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (  3 monezi)         0   0   0   1   1
        Gramada 3 (  0 monezi)         0   0   0   0   0
        Gramada 4 (  1 monezi)         0   0   0   0   1
        Gramada 5 (  4 monezi)         0   0   1   0   0

Efectuand XOR-ul se va constata ca pe coloanele 3, 4, 5 vom avea 1. Inlocuim linia 5 cu 0 0 0 1 1 (luam monezi astfel incat in gramada 5 sa ramana 3 obiecte).


In gramada 5 mai am 3 obiecte si dupa cum se poate observa calculatorul a luat 1 obiect din gramada 4. Matricea binara arata astfel:
        Gramada 1 (  1 moneda)        0   0   0   0   1
        Gramada 2 (  3 monezi)         0   0   0   1   1
        Gramada 3 (  0 monezi)         0   0   0   0   0
        Gramada 4 (  0 monezi)         0   0   0   0   0
        Gramada 5 (  3 monezi)         0   0   0   1   1

Efectuand XOR-ul se va constata ca pe coloana 5 vom avea 1. Inlocuim linia 1 cu 0 0 0 0 0 (in gramada 1 nu mai ramane nici un obiect).


In gramada 1 nu mai am nici un obiect si dupa cum se poate observa calculatorul a luat 1 obiect din gramada 2. Matricea binara arata astfel:
        Gramada 1 (  0 monezi)        0   0   0   0   0
        Gramada 2 (  2 monezi)         0   0   0   1   0
        Gramada 3 (  0 monezi)         0   0   0   0   0
        Gramada 4 (  0 monezi)         0   0   0   0   0
        Gramada 5 (  3 monezi)         0   0   0   1   1

Efectuand XOR-ul se va constata ca pe coloana 5 vom avea 1. Inlocuim linia 5 cu 0 0 0 1 0 (in gramada 5 vor ramane 2 obiecte).


In gramada 5 au ramas 2 obiecte si dupa cum se poate observa calculatorul a luat 1 obiect din gramada 2. Matricea binara arata astfel:
        Gramada 1 (  0 monezi)        0   0   0   0   0
        Gramada 2 (  1 moneda)        0   0   0   0   1
        Gramada 3 (  0 monezi)         0   0   0   0   0
        Gramada 4 (  0 monezi)         0   0   0   0   0
        Gramada 5 (  2 monezi)         0   0   0   1   0

Efectuand XOR-ul se va constata ca pe coloana 4, 5 vom avea 1. Inlocuim linia 5 cu 0 0 0 0 1 (in gramada 5 mai ramane 1 obiect).


In gramada 5 a ramas 1 obiect si dupa cum se poate observa calculatorul a luat 1 obiect din gramada 2. Matricea binara arata astfel:
        Gramada 1 (  0 monezi)        0   0   0   0   0
        Gramada 2 (  1 moneda)        0   0   0   0   1
        Gramada 3 (  0 monezi)         0   0   0   0   0
        Gramada 4 (  0 monezi)         0   0   0   0   0
        Gramada 5 (  2 monezi)         0   0   0   1   0

Efectuand XOR-ul se va constata ca pe coloana 4, 5 vom avea 1. Inlocuim linia 5 cu 0 0 0 0 1 (in gramada 5 mai ramane 1 obiect).

A ramas o singura moneda si e randul dumneavoastra...Ati castigat!!