Bulletin of the Australian Mathematical Society

Research Article

A RESTRICTION OF EUCLID

GRANT CAIRNSa1 c1 and NHAN BAO HOa2

a1 Department of Mathematics and Statistics, La Trobe University, Melbourne 3086, Australia (email: G.Cairns@latrobe.edu.au)

a2 Department of Mathematics and Statistics, La Trobe University, Melbourne 3086, Australia (email: nbho@students.latrobe.edu.au, honhanbao@yahoo.com)

Abstract

Euclid is a well-known two-player impartial combinatorial game. A position in Euclid is a pair of positive integers and the players move alternately by subtracting a positive integer multiple of one of the integers from the other integer without making the result negative. The player who makes the last move wins. There is a variation of Euclid due to Grossman in which the game stops when the two entries are equal. We examine a further variation which we called M-Euclid where the game stops when one of the entries is a positive integer multiple of the other. We solve the Sprague–Grundy function for M-Euclid and compare the Sprague–Grundy functions of the three games.

(Received November 30 2011)

2010 Mathematics subject classification

  • primary 91A46; secondary 97A20

Keywords and phrases

  • combinatorial game theory;
  • Sprague–Grundy function;
  • Euclid

Correspondence:

c1 For correspondence; e-mail: G.Cairns@latrobe.edu.au