We investigate two modifications to the traditional rules of Wythoff Nim, a combinatorial game. In Wythoff Nim, players take turns removing stones from a pair of piles. In each turn, a player chooses to either (1) take any number of stones from one pile or (2) take an equal number from both. The player removing the last stone wins. A seminal result of Wythoff states that at any point in the game, the current player is in a P-position — that is, guaranteed to lose assuming the other player plays optimally — if and only if the pair of pile sizes is of the form ([øn], [ø²n]) for some n  ∈ ℕ, where ø = 1.618 … represents the golden ratio.

This thesis introduces a variant of Wythoff Nim, which we call W(a, b), characterized by positive integers a and b, where players' moves are constrained to either removing a multiple of a from the first pile, a multiple of b from the second, or an equal number from both. We prove that the P-positions of this variant also follow sloping "beams", but with slopes determined by a and b.

Additionally, we explore the consequences of modifying Wythoff's Nim by introducing additional fixed winning and losing positions. Our empirical observations suggest a convergence of the P-positions in the long run, resembling those of the regular Wythoff game. Together, these results shed light on the applicability of Wythoff's theory to variants of his original game.

51 pages

Thesis Committee:
Danny Sleator (Chair)
Klaus Sutner

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu