Gra NIM – niekończąca się historia

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.

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,...