Variations of the Game 3-Euclid

We present two variations of the game 3-Euclid. The games involve a triplet of positive integers. Two players move alternately. In the first game, each move is to subtract a positive integer multiple of the smallest integer from one of the other integers as long as the result remains positive. In the second game, each move is to subtract a positive integer multiple of the smallest integer from the largest integer as long as the result remains positive. The player who makes the last move wins. We show that the two games have the same -positions and positions of Sprague-Grundy value 1. We present three theorems on the periodicity of -positions and positions of Sprague-Grundy value 1. We also obtain a theorem on the partition of Sprague-Grundy values for each game. In addition, we examine the misère versions of the two games and show that the Sprague-Grundy functions of each game and its misère version differ slightly. 1. Introduction The game Euclid, introduced by Cole and Davie [1], is a two-player game based on the Euclidean algorithm. A position in Euclid is a pair of positive integers. The two players move alternately. Each move is to subtract from one of the entries a positive integer multiple of the other without making the result negative. The game stops when one of the entries is reduced to zero. The player who makes the last move wins. In the literature, the term Euclid has been also used for a variation presented by Grossman [2] in which the game stops when the two entries are equal. More details and discussions on Euclid and Grossman’s game can be found in [3–9]. Some restrictions of Grossman’s game can be found in [10–12]. The misère version of Grossman’s game was studied in [13]. Collins and Lengyel [11] presented an extension of Grossman’s game to three dimensions that they called 3-Euclid. In 3-Euclid, a position is a triplet of positive integers. Each move is to subtract from one of the integers a positive integer multiple of one of the others as long as the result remains positive. Generally, from a position , where , there are three types of moves in 3-Euclid: (i) 1-2 moves: subtracting a multiple of from ; (ii) 1–3 moves: subtracting a multiple of from ; (iii) 2-3 moves: subtracting a multiple of from . In this paper, we present two restrictions of Collins and Lengyel’s game. In the first restriction that we call , a move is to subtract a positive integer multiple of the smallest integer from one of the other integers as long as the result remains positive. In the second restriction that we call , each move is to subtract a positive