Grundy's Game

Grundy's Game is played with one or more heaps of items. The nature of the items is not important, but in the applet below they may perhaps remind of chocolate squares. The only legal move in the game is to split a single heap into smaller two of different sizes.

To perform a move click between any two (with the above provision) adjacent squares.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

Explanation

|Activities| |Contact| |Front page| |Contents| |Games|

Copyright © 1996-2017 Alexander Bogomolny

Grundy's Game

Clearly the game ends when all the heaps have either one or two items. The Grundy number of heaps of size 0, 1, 2 is 0. By the Mex rule, that of the heap of size 3 is 1. For other sizes the Grundy numbers are found successively: 0, 0, 0, 1, 0, 2, 1, ... Here is a list of values for heap sizes up to 60 [WW, p. 96]:

0-90 0 0 1 0 2 1 0 2 1
10-190 2 1 3 2 1 3 2 4 3
20-290 4 3 0 4 3 0 4 1 2
30-393 1 2 4 1 2 4 1 2 4
40-491 5 4 1 5 4 1 5 4 1
50-590 2 1 0 2 1 5 2 1 3

As usual, the P-positions are those whose Grundy number is 0. You are bound to win the game if, on every move, you leave a P-Position.

References

  1. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001
  2. J. H. Conway, On Numbers And Games, A K Peters, 2001
  3. R. Guy, fair game, Comap's Explorations in Mathematics, 1989

Related material
Read more...

  • What Is a Combinatorial Game?
  • A Game of Candy Squares
  • A Sticky Problem
  • Another Sticky Problem
  • Date Game
  • Dawson's Chess: an Interactive Gizmo
  • Dawson's Kayles: an Interactive Gizmo
  • Hex 7
  • Kayles
  • Nimble: an Interactive Gizmo
  • Northcott's game (An Interactive Gizmo)
  • Odd Scoring
  • One Pile: an Interactive Gizmo
  • Plainim (An Interactive Gizmo)
  • Plainim Misere (An Interactive Gizmo)
  • Scoring: the simplest of the impartial games
  • Scoring Misere: an Interactive Gizmo
  • Scoring Misere: Two Heaps Perfect Strategy
  • The Fraction Game
  • The Silver Dollar Game
  • Silver Dollar Game With No Silver Dollar
  • Subtraction Game
  • TacTix: an Interactive Gizmo
  • Turning Turtles
  • Take-Away Games
  • Wythoff's Nim, Literal Implementation
  • Wythoff's Nim (An Interactive Gizmo)
  • |Activities| |Contact| |Front page| |Contents| |Games|

    Copyright © 1996-2017 Alexander Bogomolny

     62645182

    Search by google: