On remoteness functions of exact slow NIM, NIM^1 =(4,2) and NIM^1 =(5,2)
DOI:
https://doi.org/10.64700/mmm.104Keywords:
Remoteness function, Sprague-Grundy function, slow NIMAbstract
Given integer $n$ and $k$ such that $0<k<n$ and $n$ piles of stones, two players make moves alternately, reducing by every move exactly $k$ piles from $n$, by one stone each. The player who must move but cannot is the loser. We call this game exact slow NIM and denote it $\mathrm{NIM}^1(n, k)$. In recent articles [25,26,27,28], a very simple explicit rule was suggested choosing a move in each position of this game. Furthermore, in case $n=k+1$, it was proven that each move chosen by this rule reduces the Smith's remoteness function of the game exactly by one. This result allows us to compute the remoteness function efficiently, thus, solving the game. In the present article, we apply the same rule for two new cases: $k=2, n=4,5$ and show that it still works efficiently: The remoteness function is reduced by one with almost every move. Exceptions are sparse and have a regular pattern. We suggest simple formulas explaining all known exceptions and, thus, solve the two considered new families of games too.
References
[1] M. H. Albert, R. J. Nowakowski and D. Wolfe: Lessons in play: An introduction to combinatorial game theory, A. K. Peters, Massachusetts (2007).
[2] E. R. Berlekamp, J. H. Conway and R. K. Guy: Winning ways for your mathematical plays, 4, A. K. Peters, Massachusetts (2004).
[3] E. Boros, V. Gurvich, N. B. Ho and K. Makino: On the Sprague-Grundy function of extensions of proper NIM, Internat. J. Game Theory, 50 (3) (2021), 635–654.
[4] E. Boros, V. Gurvich, N. B. Ho, K. Makino and P. Mursiˇc: Sprague-Grundy function of matroids and related hypergraphs, Theor. Comput. Sci., 799 (2019), 40–58.
[5] E. Boros, V. Gurvich, K. Makino and M. Vyalyi: Computing remoteness functions of Moore,Wythoff, and Euclid’s games, Int. J. Game Theory, 53 (4) (2024), 1315–1333.
[6] E. Boros, V. Gurvich and V. M. Oudalov: A polynomial algorithm for a two-parameter extension of Wythoff NIM based on the Perron-Frobenius theory, Int. J. Game Theory, 42 (4) (2013), 891–915.
[7] C. L. Bouton: Nim, a game with a complete mathematical theory, Ann. of Math., 3 (1–4) (1901-1902), 35–39.
[8] N. Chikin, V. Gurvich, K. Knop, M. Paterson and M. Vyalyi: More about exact slow k-nim, Integers, 21 (2021), 1–14.
[9] A. J. Cole, A. J. T. Davie: A game based on the Euclidean algorithm and a winning strategy for it, Math. Gaz., 53 (1969), 354–357.
[10] D. Collins: Variations on a theme of Euclid, Integers, 5 (2005), 1–12.
[11] J. H. Conway: On numbers and games, Academic Press, London (1976).
[12] H. S. M. Coxeter: The golden section, Phyllotaxis and Wythoff’s game, Scripta Math., 19 (1953), 135–143.
[13] A. S. Fraenkel, I. Borosh: A generalization of Wythoff’s game, J. Combin. Theory Ser. A, 15 (2) (1973), 175–191.
[14] A. S. Fraenkel: How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly, 89 (1982), 353–361.
[15] A. S. Fraenkel: Wythoff games, continued fractions, cedar trees and Fibonacci searches, Theoret. Comput. Sci., 29 (1984), 49–73.
[16] A. S. Fraenkel: Euclid and Wythoff games, Discrete Math., 304 (2005), 65–68.
[17] P. M. Grundy, C. A. B. Smith: Disjunctive games with the last player losing, Math. Proc. Cambridge Philos. Soc., 52 (1956), 527–533.
[18] P. M. Grundy: Mathematics of games, Eureka, 2 (1939), 6–8.
[19] V. Gurvich: On the misère version of game Euclid and miserable games, Discrete Math., 307 (9-10) (2007), 1199–1204.
[20] V. Gurvich: Miserable and strongly miserable impartial games, RUTCOR Research Report 18-2011, Rutgers University (2011).
[21] V. Gurvich: Further generalizations of the Wythoff game and minimum excludant, Discrete Appl. Math., 160 (2012), 941–947.
[22] V. Gurvich, N. B. Ho: Slow k-Nim, RUTCOR Research Report 3-2015, Rutgers University (2015), http://arxiv.org/abs/1508.05777.
[23] V. Gurvich, N. B. Ho: On tame, pet, domestic, and miserable impartial games, Discrete Appl. Math., 243 (2018), 54–72.
[24] V. Gurvich, S. Heubach, N. B. Ho and N. Chikin: Slow k-Nim, Integers, 20 (2020), 1–19.
[25] V. Gurvich, M. Naumova: GM-rule and its applications to impartial games, arXiv 2311.03257, (2023).
[26] V. Gurvich, D. Martynov, V. Maximchuk and M. Vyalyi: On remoteness functions of exact slow k-NIM with k+1 piles, Integers, 24 (2024), 1–21.
[27] V. Gurvich, V. Maximchuk, G. Miheenkov and M. Naumova: On remoteness functions of exact slow k-NIM with k+1 piles in normal and misère versions, Games, 15 (6) (2024), Article ID:37.
[28] V. Gurvich, M. Naumova: Screw discrete dynamical systems and their applications to exact slow NIM, Discrete Appl. Math., 358 (2024), 382–394.
[29] V. Gurvich, M. Vyalyi: On computational hardness of multidimensional subtraction games, Algorithms, 14 (3) (2021), Article ID:71.
[30] T. A. Jenkyns, J. P. Mayberry: The skeleton of an impartial game and the Nim-function of Moore’s Nimk, Internat. J. Game Theory, 9 (1) (1980), 51–63.
[31] T. Lengyel: A Nim-type games and continued fraction, Fibonacci Quart., 41 (2003), 310–320.
[32] T. Lengyel: On calculating the Sprague-Grundy function for the game Euclid, Proc. 11th Int. Conf. on Fibonacci Numbers and Their Applications, Braunschweig (Germany) (2004), 169–175.
[33] R. Lenhardt: Composite mathematical games, Bachelor Thesis, Comenius University, Bratislava (2007).
[34] E. H. Moore: A generalization of the game called Nim, Ann. of Math., 11 (3) (1910), 93–94.
[35] J. von Neumann, O. Morgenstern: Theory of games and economic behavior, Princeton University Press, Princeton (1944).
[36] G. Nivasch: More on the Sprague–Grundy function for Wythoff’s game, Games of No Chance 3, MSRI Publications, 56 (2009), 377-410.
[37] G. Nivasch: The Sprague–Grundy function of the game Euclid, Discrete Math., 306 (21) (2006), 2798–2800.
[38] G. Nivasch: The Sprague–Grundy function forWythoff’s game: On the location of the q-values, Master Thesis,Weizmann Institute of Sciences, Rehovot (2004).
[39] C. A. B. Smith: Graphs and composite games, J. Combin. Theory, 1 (1966), 51–81.
[40] E. L. Spitznagel Jr.: Properties of a game based on Euclid’s algorithm, Math. Mag., 46 (1973), 87–92.
[41] R. Sprague: Über mathematische Kampfspiele, Tohoku Math. J., 41 (1936), 438–444.
[42] P. D. Straffin: A Nim-type game, solution to problem # 1537, Math. Mag., 71 (1998), 394–395.
[43] W. A. Wythoff: A modification of the game of Nim, Nieuw Arch. Wisk, 7 (1907), 199–202.
[44] A. M. Yaglom, I. M. Yaglom: Challenging mathematical problems with elementary solutions vol. II, Holden-Day, London (1967).
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Vladimir Gurvich, Vladislav Maximchuk, Mariya Naumova
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
