×

On the misere version of game Euclid and miserable games. (English) Zbl 1108.91019

Summary: Recently, Gabriel Nivasch got the following remarkable formula for the Sprague-Grundy function of game Euclid: \(g^+(x,y)=\lfloor |x/y-y/x| \rfloor\) for all integers \(x\), \(y\geq 1\). We consider the corresponding misere game and show that its Sprague-Grundy function \(g^-(x,y)\) is equal to \(g^+(x,y)\) for all positions \((x,y)\), except for the case when \((x,y)\) or \((y,x)\) equals \((kF_i,kF_{i+1})\), where \(F_i\) is the \(i\)th Fibonacci number and \(k\) is a positive integer. It is easy to see that these exceptional Fibonacci positions are exactly those in which all further moves in the game are forced (unique) and hence, the results of the normal and misere versions are opposite; in other words, for these positions \(g^+\) and \(g^-\) take values 0 and 1 so that \(g^-=1-g^+=(-1)^{i+1}+ g^+\).
Let us note that the good old game of Nim has similar property: if there is at most one bean in each pile then all further moves are forced. Hence, in these forced positions the results of the normal and misere versions are opposite, while for all other positions they are the same, as it was proved by Charles Bouton in 1901. Respectively, in the forced positions \(g^+\) and \(g^-\) take values 0 and 1 so that \(g^-=1-g^+=(-1)^{i+1}+g^+\), where \(i\) is the number of non-empty piles, while in all other positions \(g^+\equiv g^-\).

MSC:

91A46 Combinatorial games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banerji, A. J.; Dunning, C. A., On misere games, Cybernet. Systems, 23, 221-228 (1992) · Zbl 0756.90094
[2] E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, vols. 1-4, second ed., A.K. Peters, Natick, MA, 2001-2004.; E.R. Berlekamp, J.H. Conway, R.K. Guy, Winning Ways for Your Mathematical Plays, vols. 1-4, second ed., A.K. Peters, Natick, MA, 2001-2004. · Zbl 1084.00002
[3] Blass, U.; Fraenkel, A. S., The Sprague-Grundy function for Wythoff’s game, Theoret. Comput. Sci., 75, 311-333 (1990) · Zbl 0701.68037
[4] Bouton, C. L., Nim, a game with a complete mathematical theory, Ann. of Math., 3, 35-39 (1901-1902), (second series) · JFM 32.0225.02
[5] Cole, A. J.; Davie, A. J.T., A game based on the Euclidean algorithm and a winning strategy for it, Math. Gaz., 53, 354-357 (1969) · Zbl 0186.25303
[6] Collins, D., Variations on a theme of Euclid, integers, Electron. J. Comb. Number Theory, 5, #G03, 1-12 (2005), \( \langle\) http://www.integers-ejcnt.org/vol5.html \(\rangle \) · Zbl 1121.91022
[7] Conway, J. H., On Numbers and Games (1976), Academic Press: Academic Press London, New York, San Francisco · Zbl 0334.00004
[8] Fergusson, T. S., On sums of graph games with last player loosing, Internat. J. Game Theory, 3, 159-167 (1974) · Zbl 0306.90089
[9] T.S. Fergusson, Misere annihilation games, J. Combin. Theory Ser. A (1984) 205-230.; T.S. Fergusson, Misere annihilation games, J. Combin. Theory Ser. A (1984) 205-230. · Zbl 0546.90110
[10] Fraenkel, A. S., How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly, 89, 353-361 (1982) · Zbl 0504.90087
[11] Fraenkel, A. S., Wythoff games, continued fractions, cedar trees and Fibonacci searches, Theoret. Comput. Sci., 29, 49-73 (1984) · Zbl 0557.90107
[12] A.S. Fraenkel, Euclid and Wythoff Games. Technical Report MCS05-02, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, \( \langle;\) http://wisdomarchive.wisdom.weizmann.ac.il:81/archive/00000370/01/05-02.pdf \(\rangle;\); A.S. Fraenkel, Euclid and Wythoff Games. Technical Report MCS05-02, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, \( \langle;\) http://wisdomarchive.wisdom.weizmann.ac.il:81/archive/00000370/01/05-02.pdf \(\rangle;\)
[13] Fraenkel, A. S.; Borosh, I., A generalization of Wythoff’s game, J. Combin. Theory, 15, 135-143 (1973) · Zbl 0265.90065
[14] Grossman, J. W., Problem # 1537, Math. Mag., 70, 382 (1997)
[15] Grundy, P. M., Mathematics of games, Eureka, 2, 6-8 (1939)
[16] Grundy, P. M.; Smith, C. A.B., Disjunctive games with the last player losing, Proc. Cambridge Philos. Soc., 52, 523-527 (1956) · Zbl 0074.34504
[17] Lengyel, T., A Nim-type games and continued fraction, Fibonacci Quart, 41, 310-320 (2003) · Zbl 1046.05500
[18] T. Lengyel, On calculating the Sprague-Grundy function for the game Euclid, Proceedings of the 11th International Conference on Fibonacci Numbers and Their Applications, July 5-9, 2004, Technical University of Carolo-Wilhelmina, Braunschweig, Germany (2004), 169-175. http://faculty.oxy.edu/ lengyel/papers/FQ112233v52.pdf; T. Lengyel, On calculating the Sprague-Grundy function for the game Euclid, Proceedings of the 11th International Conference on Fibonacci Numbers and Their Applications, July 5-9, 2004, Technical University of Carolo-Wilhelmina, Braunschweig, Germany (2004), 169-175. http://faculty.oxy.edu/ lengyel/papers/FQ112233v52.pdf
[19] von Neumann, J.; Morgenstern, O., Theory of Games and Economic Behavior (1944), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0063.05930
[20] Nivasch, G., The Sprague-Grundy function of the game Euclid (2004), Manuscript, \( \langle\) http://www.yocs.org/ gnivasch/euclid/index.html \(\rangle \) · Zbl 1201.91020
[21] G. Nivasch, The Sprague-Grundy function for Wythoff’s game: On the location of the \(q\langle;\) http://www.wisdom.weizmann.ac.il/gabrieln \(\rangle;\); G. Nivasch, The Sprague-Grundy function for Wythoff’s game: On the location of the \(q\langle;\) http://www.wisdom.weizmann.ac.il/gabrieln \(\rangle;\)
[22] T.E. Plambeck, Pretending in misere combinatorial games, Manuscript, 2003, \( \langle;\) http://www.plambeck.org/oldhtml/mathematics/games/misere \(\rangle;\); T.E. Plambeck, Pretending in misere combinatorial games, Manuscript, 2003, \( \langle;\) http://www.plambeck.org/oldhtml/mathematics/games/misere \(\rangle;\)
[23] T.E. Plambeck, Taming the wild in impartial combinatorial games, Manuscript, 2005, \( \langle;\) http://www.plambeck.org/oldhtml/mathematics/games/misere \(\rangle;\); T.E. Plambeck, Taming the wild in impartial combinatorial games, Manuscript, 2005, \( \langle;\) http://www.plambeck.org/oldhtml/mathematics/games/misere \(\rangle;\) · Zbl 1092.91012
[24] Spitznagel, E. L., Properties of a game based on Euclid’s algorithm, Math. Mag., 46, 87-92 (1973) · Zbl 0268.90067
[25] Sprague, R., Über mathematische Kampfspiele, Tohoku Math. J., 41, 438-444 (1936) · Zbl 0013.29004
[26] Straffin, P. D., A Nim-type game, solution to problem # 1537, Math. Mag., 71, 394-395 (1998)
[27] Wythoff, W. A., A modification of the game of Nim, Niew Archief voor Wiskunde, 7, 199-202 (1907) · JFM 37.0261.03
[28] Yamasaki, Y., On misere Nim-type games, J. Math. Soc. Japan, 32, 461-475 (1980) · Zbl 0434.90108
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.