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

Otwarty dostęp , Pomysł na lekcję

18 marca 2021

NR 48 (Marzec 2021)

Gra nim i jej krewni

62

Gra Nim to jeden z ciekawszych matematycznych „obiektów”. Jej zaletami są proste reguły i możliwość odgadnięcia teorii w wielu przypadkach. Uczniowie mogą sami odkrywać strategie gry zapewniające zwycięstwo.

Klasyczna gra Nim

Wikipedia podaje, że Nim to stara chińska gra dla dwóch osób (Jianshizi, czyli „gra w zabieranie kamieni”). Załóżmy, że mamy n stosów kamieni: w pierwszym stosie jest a1 kamieni, w drugim a2, …, w n-tym an kamieni. Dwaj gracze (rozpoczynającego nazwij­-
my A, grającego 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 1 lub 2, …, lub ai kamieni. Wygrywa ten gracz, który weźmie ostatni (ostatnie kamienie). Opisaną klasyczną wersję gry Nim oznaczać będziemy Nim (a1, a2, …, an).
Gra Nim jest grą strategiczną, nie ma w niej remisów; istnieje także wersja tej gry (nazywa się ją misère, co z francuskiego można przetłumaczyć jako uboga), w której przegrywa ten gracz, który weźmie ostatni kamień. Naszym zadaniem jest opisanie strategii gry Nim, tzn. metody, która jednemu z graczy zapewnia zwycięstwo – oczywiście pod warunkiem, że nie popełnia błędów.

POLECAMY

Odkrywanie strategii gry Nim

Jasne jest, że w grze Nim, gdy jest tylko jeden stos kamieni, wygrywa gracz A. Warto poprosić uczniów o uzasadnienie, warto także zapytać ich o grę w wersji misère. Kolejny etap to gra Nim z dwoma stosami. Tutaj też uczniowie poradzą sobie z teorią: gdy oba stosy są równoliczne, to wygrywa gracz B, w przeciwnym przypadku gracz A. Nieco trudniej znaleźć odpowiedź dla wersji misère – tutaj przy równolicznych stosach wygrywa też gracz B, dla nierównolicznych gracz A.
Zajmijmy się teraz grami Nim (a1, a2, a3). Zadaniem uczniów jest odkrycie teorii i strategii, przy czym warto podzielić pracę nad grą z trzema stosami na trzy przypadki:

  • Nim (a1, a1, a1); trzy stosy mają jednakową liczbę elementów, uczniowie bez trudu poradzą sobie z uzasadnieniem, że w tej grze wygrywa A – wystarczy, że weźmie cały jeden stos, doprowadzając do gry z dwoma jednakowymi stosami, w tej „nowej” grze gracz A staje się graczem B i powtarza ruchy swojego przeciwnika. Taka analiza będzie powtarzana wielokrotnie, jeśli gracz A ma strategię zwycięską, to powinien wykonać ruch do takiej pozycji, w której drugi gracz powinien wygrać. Natomiast istnienie strategii zwycięskiej dla B oznacza, że niezależnie od ruchu przeciwnika doprowadza zawsze do pozycji zwycięskiej dla pierwszego gracza, którym po ruchu A staje się gracz B.
  • Nim (a1, a1, a2); analizę pozostawiamy Czytelnikowi.
  • Nim (a1, a2, a3), przy czym liczby a1, a2, a3 są różne (bez zmniejszania ogólności możemy zakładać, że a1 < a2, < a3).

Rozpatrzmy na przykład grę Nim (1, 2, 3). Jasne jest, że wzięcie przez A któregoś całego stosu prowadzi do jego porażki (Dlaczego?), zatem gracz A powinien spróbować zmniejszyć drugi lub trzeci stos. Spójrzmy na możliwości takiego ruchu dla gracza A:
(1, 2, 3) → (1, 1, 3) – gracz A zmniejszył drugi stos o 1. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 0, 3) – gracz A zabrał cały drugi stos. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 2) – gracz A zmniejszył trzeci stos o 1. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 1) – gracz A zmniejszył trzeci stos o 2. Jaki ruch powinien wykonać B, aby wygrać?
(1, 2, 3) → (1, 2, 0) – gracz A zabrał cały trzeci stos. Jaki ruch powinien wykonać B, aby wygrać?

Z przeprowadzonej analizy wynika, że zwycięzcą gry Nim (1, 2, 3), przy dobrej grze, jest gracz B, co zapiszemy tak: z (Nim (1, 2, 3)) = B. Zauważmy, że z (Nim (1, 2, n)) = A dla dowolnego n ≥ 4. Czytelnik zechce to sprawdzić sam, podając przy tym pierwszy zwycięski ruch gracza A.

Gra Nim – teoria

Teorię gry Nim opracował amerykański matematyk Charles L. Bouton; jego artykuł Nim, A Game with a Complete Mathematical Theory został opublikowany w „The Annals of Mathematics” 2 nd ser., v. 3, nr 1/4, 1901–1902, str. 35–39. Bouton w artykule tym wspomina, że podobną teorię opisał Paul E. More w 1899 roku, ale nie podał on żadnych dowodów. W rozumowaniu Boutona pojawiła się funkcja, którą definiuje się tak: 
Dwie liczby naturalne m, n zapisujemy w systemie dwójkowym i dodajemy modulo 2, tzn.:
nimsuma (m, n) = (m1, …, mk)2 + (n1, …, nk)2 = (m1 + n1 (mod 2), …, mk + nk (mod 2));
np. nimsuma (2, 4) = (0, 1, 0)2 + (1, 0, 0)2 = (1, 1, 0). 

Zauważmy, że jeśli liczby cyfr liczb w zapisie dwójkowym są różne, to wyrównujemy je, dopisując z przodu „krótszej” liczby odpowiednią liczbę zer.
Funkcję nimsuma możemy zastosować także dla trzech, czterech, … liczb. Bouton zauważył, że nimsuma (a1, a2, …, an) jednoznacznie wskazuje, kto powinien wygrać, A czy B. Sprawdźmy to dla dwóch oraz dla trzech stosów.


W grze Nim (a1, a2, …, an) wygrywa gracz A wtedy i tylko wtedy, gdy nimsuma (a1, a2, …, an) zawiera co najmniej jedną cyfrę 1. 

Dowód tego twierdzenia (ma ono formę równoważności) nie jest trudny, zwłaszcza wynikanie ⇒. Można rozumować tak: gdy nimsuma (a1, a2, …, an) = 
= (0, … , 0), to po każdym ruchu gracza A otrzymujemy grę z nimsumą niezerową, a to znaczy, że gracz rozpoczynający w nowej pozycji (B) powinien wygrać. Kluczowy jest dowód ⇐; A powinien znaleźć odpowiedni stos oraz wziąć z niego tyle kamieni, aby po tym ruchu otrzymać grę z zerową nimsumą. Wiemy, że na przykład dla gry Nim (1, 2, 4) wzięcie jednego kamienia z trzeciego stosu to jedyny ruch A przynoszący mu zwycięstwo, dlatego wybór stosu jest istotny. W praktyce rozumujemy tak: ponieważ spełniony jest warunek nimsuma (a1, a2, …, an) = (cn, cn − 1, …, c1) ≠ (0, …, 0), weźmy największe takie k, że ck ≠ 0. Oznaczmy przez aʹk liczbę, której zapis dwójkowy jest równy nimsuma (ak, (cn, cn − 1, …, c1)). Wtedy z k-tego stosu należy wziąć taką liczbę, aby w stosie tym pozostało aʹk elementów. Dla ilustracji tej procedury spójrzmy jeszcze raz na Nim (1, 2, 4); zauważmy, że nimsuma (1, 2, 4) = (1, 1, 1), zatem k = 3 oraz aʹ3 = 3 = (0, 1, 1)2 (ze stosu numer 3 zabieramy jeden kamień). 

Marienbad

Jednym z wariantów Nima jest gra Marienbad, którą Wikipedia opisuje tak:

16 pionów ustawiamy w 4 rzędach: rząd nr 1 – 1 pionek; rząd nr 2 – 3 pionki; rząd nr 3 – 5 pionków; rząd nr 4 – 7 pionków. Ruch polega na wzięciu od jednego pionka do całego rzędu. Przegrywa gracz, który zabiera ostatni pionek.

Zauważmy, że Marienbad jest wersją misère gry Nim (1, 3, 5, 7). Gra ta wzbudziła spore poruszenie w warszawskim środowisku matematycznym, ale nie z powodów artystycznych. Wojciech Guzicki w artykule Zeszłego roku w Marienbadzie („Matematyka” 2-23/1990, str. 100–110) pisze, że on i wielu jego kolegów było na filmie właśnie o takim tytule dwa razy: w filmie jeden z bohaterów zapraszał gości do tej gry i ...

Artykuł jest dostępny w całości tylko dla zalogowanych użytkowników.

Jak uzyskać dostęp? Wystarczy, że założysz bezpłatne konto lub zalogujesz się.
Czeka na Ciebie pakiet inspirujących materiałow pokazowych.
Załóż bezpłatne konto Zaloguj się

Przypisy