Euclid's Game on a Square Grid

The game starts with two integers selected randomly on a square grid. The players (of which the computer is one) take turns picking up two of the already selected numbers and marking the difference between the larger and the smaller of the two, provided of course that number has not been marked previously. The player unable to move loses the game.

As you play against the computer, you may force it to make the first move by pressing "You start" button.

(This is a reincarnation of Euclid's Game, as proposed at Let's Play Math blog.)

Explanation

|Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny

The underlying idea of the game is Euclid's algorithm for finding the greatest common divisor (or factor) of two positive integers. It can be expressed in algorithmic form:

function gcd(N, M) {
  if M is 0
    return N
  otherwise
    return gcd(M, N mod M)
}

For example, let N = 40 and M = 12. Euclid's algorithm is expressed in terms of modulo arithmetic.

Then, on the first step, 40 ≡ 4 (mod 12), giving gcd(40, 12) = gcd(12, 4).

On the second step, 12 ≡ 0 (mod 4), giving gcd(12, 4) = gcd(4, 0).

With M = 0, the algorithm returns 4 as the gcd of 12 and 4 and of 40 and 12.

How this relates to the game. Assume it starts with 40 and 12 marked. Whoever plays now has only one choice - the difference 40 - 12 = 28. With three numbers on the board, we may now mark 28 - 12 = 16 and then also 16 - 12 = 4. This makes possible to eventually mark 36 = 40 - 4, 32 = 36 - 4, and so on.

4 is the smallest number to appear on the board and, when the game is over, all its multiples below 40 will be marked.

A longer way to implement Euclid's algorithm is to keep subtracting the smaller of the two numbers from the larger one until one of them becomes 0, at which point the remaining non-zero number is the greatest common factor of the original pair.

function gcd(N, M) {
  if N is greater than M
    return gcd(N - M, M)
  else if M is greater than N
    return gcd(M - N, N)
  otherwise 
    return M
}

So, almost as in the game, with N = 40 and M = 12, we have successively

|Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2012 Alexander Bogomolny