Wythoff's game

Wythoff's game is a two-player mathematical game of strategy, played with two piles of counters. Players take turns removing counters from one or both piles; in the latter case, the numbers of counters removed from each pile must be equal. The game ends when one person removes the last counter or counters, thus winning.

The game is claimed to have been played in China under the name tsyan-shidzi (choosing stones). [ [http://www.cut-the-knot.org/pythagoras/withoff.shtml Wythoff's game at Cut-the-knot] ] The Dutch mathematician W. A. Wythoff, published a mathematical analysis of the game in 1907.

Mathematical theory

A "cold position" is a pair of integers ("n", "m") with "n" ≤ "m", describing the size of both piles in the position, that is a losing position for the player who is to make a move from that position. Thus to win, you should move to a cold position or the result of interchanging "n" and "m" in such a position, if that is possible. (0, 0) is a cold position. Thus, none of the positions (0, "m") and ("n", "n") for "m" > 0 and "n" > 0 are cold positions. Cold positions can be determined recursively as those from which no cold position can be reached in one move.

The first few cold positions are (0, 0), (1, 2), (3, 5), (4, 7), (6, 10). For example, from (1, 2) only these other positions can be reached: (0, 2), (1, 0) (reverse of (0, 1)), (1, 1), and (0, 1). None of these are cold positions. So (1, 2) is a cold position. The cold positions are captured in the On-Line Encyclopedia of Integer Sequences as OEIS2C|id=A000201 and OEIS2C|id=A001950. Wythoff discovered that the cold positions follow a regular pattern determined by the Golden ratio.

Specifically, if "k" is any natural number and :$n\_k\; =\; lfloor\; k\; phi\; floor\; ,$:$m\_k\; =\; lfloor\; k\; phi^2\; floor\; =\; n\_k\; +\; k\; ,$

where &phi; is the golden ratio and we are using the floor function, then ("n"_"k", "m"_"k") is the "k"^{th cold position. Notice that "n"_"k" is the smallest natural number which does not appear as "n"_"j" or "m"_"j" for any "j" < "k".}

The proof that cold positions can be expressed in terms of the golden ratio uses the pair of complementary Beatty sequences associated with:$frac\{1\}\{phi\}\; +\; frac\{1\}\{phi^2\}\; =\; 1\; ,.$

See also

* Nim
* Golden ratio
* Grundy's game
* Subtract a square

References

External links

*MathWorld|urlname=WythoffsGame|title=Wythoff's Game