Dołącz do czytelników
Brak wyników

Matematyka w praktyce

17 września 2021

NR 51 (Wrzesień 2021)

Gra NIM – niekończąca się historia

0 26

W wielu źródłach, na przykład w marcowym tegorocznym numerze „Matematyki”, można znaleźć informacje o grze Nim. Ta prosta, ale piękna gra od wielu lat budzi zainteresowanie, zwłaszcza że pojawiło się mnóstwo jej wariantów. W artykule opiszę kilka wariantów tej gry oraz pokażę ich walory matematyczne i dydaktyczne.

Klasyczny Nim

Nim to gra, która w klasycznej postaci wygląda tak: danych jest n stosów kamieni, w pierwszym stosie jest a1 kamieni, w drugim a2, …, w n-tym an kamieni; dwaj gracze (rozpoczynający to gracz A, grający jako drugi – B) wykonują na zmianę ruchy. Każdy ruch polega na wybraniu dowolnego stosu (powiedzmy i-tego), a następnie wzięciu z tego stosu jednego lub dwóch, …, 
lub ai kamieni. Wygrywa gracz, który weźmie ostatni kamień (ostatnie kamienie). Oczywiście, zakładamy, że gracze wykonują najlepsze możliwe ruchy.

POLECAMY

Gra Euklides

Po raz pierwszy na ten wariant Nima natknąłem się, przeglądając zadania z podręcznika Lindsaya Childsa A concrete introduction to higher algebra (Springer 1979). Startujemy z dwiema liczbami naturalnymi a, b,
przy czym a ≥ b. Gracz A od liczby a odejmuje niezerową wielokrotność liczby b, tak aby różnica a − qb. była nieujemna. Grający jako drugi gracz B stosuje te same reguły dla pary a − qb,b. Wygrywa ten gracz, który otrzyma różnicę równą 0. Spójrzmy na rozgrywkę dla pary 17, 5:
A: od 17 odejmuje 3 · 5, otrzymując parę 5 („stare” b) oraz 2 (= 17 – 3 · 5),
B: od 5 odejmuje 1 · 2, otrzymując parę (3, 2),
A: od 3 odejmuje 1 · 2 i otrzymuje parę (2, 1),
B: od 2 odejmuje 2 · 1, otrzymuje różnicę 0 i wygrywa.

Zauważmy, że do analizy gry Euklides przydaje się dzielenie z resztą; dla pary (17, 5) mamy trzy dzielenia:
17 = 3 · 5 + 2,
5 = 2 · 2 + 1,
2 = 2 · 1 + 0.
W ostatniej równości celowo zapisaliśmy 0, aby podkreślić cel gry – otrzymanie różnicy 0.
Dzielenie z resztą pozwala przedstawić interpretację „kamykową” gry Euklides dla pary (17, 5); mamy wówczas trzy stosy kamieni:
 


Liczby kamieni w stosach to ilorazy z przedstawionych na poprzedniej stronie dzieleń z resztą. Podobieństwo do Nima jest ewidentne, ale różnica istotna – najpierw trzeba wyczerpać stos nr 1, potem nr 2 i, ogólnie, jeśli mamy n dzieleń, to wyczerpujemy kolejne stosy. Pojawienie się dzieleń z resztą wyjaśnia genezę nazwy gry – wiąże się ona z algorytmem Euklidesa, bowiem przedstawione dla pary (17, 5) dzielenia to właśnie algorytm Euklidesa, służący do obliczania największego wspólnego dzielnika dwóch liczb naturalnych. Wspólnie z uczniami można przeanalizować grę ze stosami 3, 2, 2. Jedyny dobry pierwszy ruch dla A to wzięcie 2 kamieni ze stosu nr 1 (uczniowie mogą to odkryć sami), wówczas B może wziąć jedynie ostatni kamień z tego stosu, potem A bierze jeden kamień ze stosu nr 2 itd.
W 1993 roku w angielskim czasopiśmie „Mathematics Teaching” ukazał się mój artykuł A cheese-cake with a raisin, w którym podałem inną interpretację gry Euklides. Znowu rozpatrujemy liczby 17 i 5, ale tym razem rysujemy prostokąt o wymiarach 17 × 5. Ten prostokąt to sernik, a w prawym górnym rogu znajduje się rodzynek, zwycięzcą zostaje ten, kto odetnie ostatni kawałek z rodzynkiem. Możliwe linie cięcia są pogrubione lub przerywane.
 


Teoria gry Euklides wiąże się z przedstawieniem ułamka a/b w postaci ułamka łańcuchowego, który w przypadku 17/5 wygląda tak:

co w notacji poziomej zapisujemy jako [3, 2, 2]. Dokładna analiza ułamka łańcuchowego odpowiadającego ułamkowi a/b pozwala znaleźć niezbyt trudną teorię gry, a dzięki niej łatwo określa się zwycięską strategię gry Euklides.

Dzielnikowy Nim

Na mojej stronie internetowej (mat.ug.edu.pl/~matpz/) w zakładce „Matematyczne eksperymenty” znajduje się następujące zadanie:
 

Dane są dwa stosy kamieni, w jednym znajduje się  m kamieni, w drugim n kamieni. Dwaj gracze (rozpoczynający A i grający jako drugi B) na zmianę wykonują ruchy, przy czym ruch polega na tym, że można wziąć z jednego z dwóch stosów liczbę kamieni, która jest dzielnikiem liczby kamieni w tym stosie. Wygrywa ten gracz, który zabierze ostatni kamień (ostatnie kamienie). Zakładając, że obaj gracze grają poprawnie, kto powinien wygrać?


Popatrzmy na rozgrywkę z czterema i trzema kamieniami w stosach:
 


W rozgrywce tej powinien wygrać gracz A – wystarczy, że weźmie jeden bordo kamień.
 


Teraz taktyka gracza A jest następująca: „naśladuje” on ruchy gracza B. Opisaną taktykę stosuje się do wszystkich dzielnikowych Nimów typu (m + 1, m), czyli wtedy, gdy liczby kamieni w obu stosach różnią się o 1. 
W konkretnych przypadkach dla niedużych liczb „rozwikłanie” gry jest łatwe, bo liczba możliwych kolejnych ruchów jest niewielka. W miarę łatwo jest odpowiedzieć, kto powinien wygrać dla pozycji typu (nieparzysta, nieparzysta), (nieparzysta, parzysta) bądź (parzysta, nieparzysta). Czytelników zainteresowanych teorią dzielnikowego Nima zapraszam na wspomnianą stronę.

Gra w układzie współrzędnych

Ten wariant gry Nim jest mi szczególnie bliski. Używałem tej gry w czasie zajęć z uczniami szkół podstawowych, wykorzystywali ją także moi studenci w czasie praktyk w szkole, ale również w trakcie swoich zajęć studenckich.
Zaczniemy od postaci tej gry przypominającej grę Nim. Mamy dwa stosy kamieni, gracze na zmianę mogą wykonać dwa typy ruchów: wzięcie jednego kamienia z dowolnie wybranego stosu albo zabranie po jednym kamieniu z każdego stosu. Wygrywa ten gracz, który weźmie ostatni kamień. Spójrzmy na przykład rozgrywki dla dwóch stosów, 4-elementowego i 5-elementowego, oraz zapiszmy przykładową rozgrywkę:
A: (4, 5) → (3, 4) (zaczynający grę wziął po jednym kamieniu z każdego ze stosów),
B: (3, 4) → (3,3) (drugi gracz wziął jeden kamień z drugiego stosu),
A: (3, 3) → (2, 3),
B: (2, 3) → (2, 2).
Ten ruch zapewnił graczowi B zwycięstwo – dlaczego?

Zaprezentujemy teraz inną postać omawianej gry. W układzie współrzędnych w pierwszej ćwiartce wybieramy punt startowy START (najlepiej punkt (0, 0)) oraz punkt końcowy META (dowolny punkt o obu współrzędnych całkowitych). Gracze na zmianę wykonują ruchy: do góry o 1, w prawo o 1 lub na ukos o wektor [1, 1] (można nie używać terminu wektor, mówiąc, że przesuwamy się o 1 do góry, a potem 1 w prawo). Wygrywa ten gracz, który pierwszy dotrze do mety. Spójrzmy na przykład z metą w punkcie (4, 5) (obrazki pochodzą z programu LOGOMOCJA, w którym napisano program do grania, wię...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy