
Ideea se aplica la orice joc unde putem gasi o strategie de joc la castig.
Fie jocul in cauza si P multimea tuturor pozitiilor care pot aparea pe
tabla de joc. Ar fi bine sa putem partitiona P in doua multimi DISJUNCTE,
P1 si P2, astfel incat:
1) Pozitia de start a jocului sa fie din P1
2) Pozitia finala sa fie din P2
3) Din orice pozitie din P1 sa existe o mutare care sa conduca intr-o
pozitie din P2
4) Din orice pozitie din P2 sa NU existe nici o mutare care sa conduca tot
intr-o pozitie din P2.
De ce urmarim aceasta partitionare? Sa ne inchipuim ca suntem jucatorul 1
si pornim din pozitia initiala (care este din P1). Atunci
- Putem gasi o mutare care sa conduca in P2 (regula 3)
- De aici, adversarul nostru, orice mutare ar face, va ajunge intr-o
pozitie din P1 (regula 4)
- Din nou noi mutam si ajungem in P1
....
Si asa mai departe. Intr-un interval finit de timp, jocul se termina.
Intrebarea este cine a facut ultima mutare. In mod sigur nu adversarul
nostru, pentru ca pozitia finala este una din P2 (regula 2), ori adversarul
nu poate lasa jocul decat intr-o pozitie din P1 (regula 4). Rezulta ca noi
am castigat.
In cazul jocului NIM, criteriul de impartire a lui P in P1 U P2 este:
"O pozitie cu N gramezi (G1, G2, ..., GN) este in P2 daca si numai daca
G1 xor G2 xor ... xor GN = 0"
Regula (1) se scrie echivalent "XOR-ul numerelor de pietre din toate
gramezile configuratiei initiale este nenul". Acest fapt a fost garantat
in enunt.
Regula (2) se scrie echivalent "XOR-ul numerelor de pietre din toate
gramezile configuratiei finale este 0". Acest fapt este evident, intrucat
configuratia finala este (0,0,...,0) si 0 xor 0 xor ... xor 0 = 0.
Demonstrati ca alegerea acestui criteriu respecta regulile 3 si 4.
Demonstratia este constructiva, in sensul ca demonstram existenta mutarii
miraculoase indicand efectiv calea de obtinere a ei.
|
|