Pierwszą z gier jest znany ludzkości od wieków Nim. Gracze wykonują ruchy na przemian, zabierając z wybranego przez siebie stosu dowolną niezerową liczbę kamieni. Gra kończy się przegraną gracza, który nie może wykonać ruchu, czyli wtedy, gdy wszystkie stosy są puste. Gra Nim pojawiała się już wielokrotnie na łamach Delty (np. w numerze 7/2010), dlatego w tym artykule ograniczymy się jedynie do przypomnienia strategii wygrywającej w tej grze. Otóż jeśli przez  oznaczymy liczności stosów w Nimie, to to, który z graczy wygra (o ile obaj grają optymalnie), zależy od wartości wyrażenia

gdzie symbol oznacza operację xor. (Aby ją wyznaczyć, zapisujemy liczby binarnie, a następnie sumujemy metodą „szkolną”, ignorując przeniesienia.) Dokładniej, pozycja w Nimie jest przegrywająca, gdy wartość powyższego wyrażenia jest równa zeru – wówczas każdy ruch prowadzi do pozycji o dodatniej wartości wyrażenia, czyli do pozycji wygrywającej. Z kolei z każdej pozycji wygrywającej istnieje co najmniej jeden ruch do pozycji przegrywającej. Tak samo można zresztą opisać grę Nim na większej liczbie stosów.

Rozważmy pewną drobną modyfikację w zasadach Nima. Gracze nadal wykonują ruchy na przemian, zabierając dowolną niezerową liczbę kamieni z wybranego przez siebie stosu. Dodatkowo jednak, jeden raz w ciągu gry każdy z nich może wykonać ruch specjalny. Wykonując taki ruch, gracz może zabrać kamienie z dwóch stosów (można więc ruch specjalny rozumieć jako wykonanie dwóch ruchów „zwykłych” pod rząd). Przegrywa, tak jak w zwykłym Nimie, gracz, który nie może wykonać ruchu. Nazwijmy tę zmodyfikowaną grę Nim 2.

Jak wygląda strategia dla gry Nim 2? Pierwszym kluczowym spostrzeżeniem jest to, iż nie opłaca się używać ruchu specjalnego, jeśli nie zakończy on gry. Spróbujmy to uzasadnić. Spójrzmy na sytuację gracza A, którego przeciwnik B wykonał jako pierwszy ruch specjalny. Jeżeli gra nie zakończyła się po ruchu gracza B, to możliwe są dwa przypadki. Gracz A mógł znaleźć się w pozycji wygrywającej w zwykłym Nimie – kontynuuje wtedy rozgrywkę, nie wykorzystując ruchu specjalnego, a strategia dla zwykłego Nima zapewnia mu zwycięstwo. Jeżeli zaś po ruchu specjalnym przeciwnika gracz A znajdzie się w pozycji przegrywającej, wykorzystuje natychmiast swój ruch specjalny. Po wykonaniu pierwszego ze „zwykłych” ruchów na pewno znajdzie się w pozycji wygrywającej, a następnie, za pomocą drugiego ruchu, może pozostawić przeciwnika w pozycji przegrywającej. Dalej gracz A gra zgodnie ze strategią dla zwykłego Nima.

Oczywistym wnioskiem z powyższego spostrzeżenia jest fakt, iż ruchu specjalnego należy użyć dopiero wtedy, gdy w grze pozostaną tylko dwa stosy. Ruch taki prowadzi wtedy do natychmiastowego zwycięstwa. Tym samym gracz, który doprowadzi do opróżnienia któregoś ze stosów, przegra. Jedyną sytuacją, w której opróżnienie stosu jest nieuniknione, jest ta, w której wszystkie trzy stosy mają liczność równą jeden. Stąd gracze powinni grać tak, jakby grali w zwykłego Nima na stosach o jeden kamień mniejszych! W ten sposób gracz, który nie może wykonać ruchu na „zmniejszonych” stosach, będzie zmuszony opróżnić jeden z (rzeczywistych) stosów i przegra.

Rys. 1 Zabranie dwóch kamieni z drugiego stosu w grze Nim 2 i odpowiadający temu ruch w 

Opiszmy to nieco bardziej formalnie. Grając w Nim 2, będziemy jednocześnie wyobrażać sobie rozgrywkę w Nim na stosach o jeden mniejszych (nazwiemy tę grę  patrz również Rys. 1). Pokażemy, że jeśli mamy strategię wygrywającą w   to mamy też strategię wygrywającą w Nim 2. Aby wykonać ruch w Nim 2, patrzymy, jaki ruch zrobilibyśmy w   a następnie powtarzamy go w Nim 2. Z kolei gdy nasz przeciwnik rusza się w Nim 2, to jeśli wykonał ruch specjalny lub opróżnił jakiś stos – z dotychczas przeprowadzonego rozumowania wiemy, że przegrał. W przeciwnym przypadku powtarzamy jego ruch w grze

Prędzej czy później doprowadzimy przeciwnika do sytuacji w   w której nie może wykonać ruchu, bo wszystkie stosy są puste. To odpowiada sytuacji w Nim 2, w której wszystkie stosy mają liczność jeden, zatem nasz przeciwnik również tutaj przegrywa.

Ostatecznie wynik w grze Nim 2 będzie zależał od wartości wyrażenia

Co ciekawe, powyższe rozumowanie nie daje się uogólnić na większą liczbę stosów. Tym samym zachęcamy Czytelników do samodzielnych prób rozwiązania uogólnionej wersji gry Nim 2!

Przyjrzymy się teraz kolejnemu wariantowi gry Nim, który nazwiemy Nim 3. Tym razem modyfikacja jest taka, że po żadnym ruchu nie mogą powstać dwa stosy o równej liczbie kamieni (zakładamy, że na początku także wszystkie stosy były różne). Gra kończy się standardowo, gdy gracze nie mogą już wykonać żadnego ruchu, a zwycięża ten, który wykonał ostatni ruch. Przy czym w tej wersji sytuacją końcową jest moment, w którym stosy mają liczność 0, 1 oraz 2.

Zastanówmy się, czy Nim 3 rzeczywiście różni się od Nima z punktu widzenia gracza, który w Nimie ma strategię wygrywającą. Przypomnijmy, że owa strategia wygrywająca w Nimie polega na zabraniu z pewnego stosu odpowiedniej liczby kamieni tak, aby xor liczności stosów z niezerowego stał się zerowy. Gdybyśmy próbowali zastosować podobną strategię tutaj, to natkniemy się na przeszkodę. Istnieją konfiguracje, w których wszystkie takie ruchy prowadzą do wyrównania liczności pewnych stosów. Są to dość charakterystyczne sytuacje, bo jeżeli  oraz, bez straty ogólności,  to  czyli jeden ze stosów musi być pusty.

Skoro już zauważyliśmy, gdzie leży trudność w zastosowaniu standardowej taktyki, to może udałoby nam się wymyślić inną grę, w której strategia wygrywająca stałaby się bardziej jasna, a odpowiednim ruchom w niej odpowiadałyby pewne ruchy w Nim 3? Problemem, na który natknęliśmy się, stosując do gry Nim 3 strategię z Nima, było to, że gdy jeden stos stał się pusty, to ruchy, które chcielibyśmy wykonać, nagle stały się ruchami zakazanymi. Pomyślmy zatem, zamiast o Nim 3, o analogicznej grze, w której ruchem zakazanym jest także opróżnianie stosów. Zauważmy, że po dołożeniu takiego wygodnego założenia już z powodzeniem możemy zastosować standardową strategię wygrywającą dla gry Nim, gdyż ruch zerujący xora liczności wszystkich stosów nigdy nie będzie prowadził do wyrównania liczności pewnych stosów, bo jak już wcześniej zauważyliśmy, implikowałoby to, że pewien ze stosów jest pusty, a założyliśmy, że tak być nie może.

To, co nam pozostało, to sztucznie zasymulować założenie o tym, że ruch opróżniający stos jest ruchem zakazanym. Sytuacją końcową w takiej grze będzie układ, w którym stosy będą miały liczności  Nasuwa się zatem pomysł, aby do każdego stosu w Nim 3 dodać po jednym wirtualnym kamieniu, którego żaden z graczy nie może zabrać. Zauważmy, że wtedy zarówno nie będzie możliwe opróżnienie stosu, bo gracz nie może zabrać wirtualnego kamienia, jak i sytuacje końcowe będą się zgadzać, bo w grze Nim 3 bez tego założenia sytuacja końcowa miała postać  Zatem już prawie osiągnęliśmy cel – mianowicie sprowadziliśmy Nima 3 do gry, w której będziemy mogli już stosować standardową taktykę znaną z Nima. Pozostaje nam jedynie formalnie udowodnić, że powyższe sprowadzenie jest rzeczywiście poprawne.

Rys. 2 Odpowiadające sobie ruchy w grach Nim 3 i

Stosujemy rozumowanie podobne jak poprzednio i, grając w Nim 3, wyobrażamy sobie rozgrywkę w grę  czyli w zwykłego Nima ze stosami zwiększonymi o jeden kamień (Rys. 2). Zakładamy, że mamy strategię wygrywającą w   i chcemy wykazać, że mamy także strategię wygrywającą w Nim 3. Tym razem każdy ruch przeciwnika w Nim 3 możemy powtórzyć w grze  Z kolei, aby wykonać nasz ruch w Nim 3, patrzymy na nasz ruch w   Ruch ten prowadzi nas do sytuacji, w której xor liczności stosów jest zerowy. Gdyby to była sytuacja, w której opróżniliśmy jeden ze stosów, to dwa pozostałe musiałyby być równe, co nie jest możliwe, gdyż w takiej sytuacji byłyby też równe na początku (co jest niezgodne z zasadami Nim 3). Zatem nasz ruch w   na pewno nie opróżni żadnego stosu, czyli jest on poprawnym ruchem w Nim 3 i możemy go tam powtórzyć.

Zauważmy, że przez całą grę w   na planszy będą stosy różnej liczności, więc w końcu doprowadzimy przeciwnika do sytuacji  co odpowiada jego przegranej w grze Nim 3 z sytuacją

Stąd wniosek, że gracz ma w grze Nim 3 strategię wygrywającą wtedy i tylko wtedy, gdy ma on strategię wygrywającą w analogicznej konfiguracji Nima z dołożonymi wirtualnymi kamieniami – po jednym do każdego stosu, czyli wynik gry zależy od wartości wyrażenia

Kwestię uogólnienia gry Nim 3 na wiele stosów zostawiamy do rozważenia Czytelnikom.