• Calendar

December 21, Tuesday
12:00 – 14:00

The game of Wythoff is a simple combinatorial game for two players. There are two piles of tokens, of sizes $x, y \ge 0$. On each turn, a player removes either any number of tokens from a single pile, or the same number of tokens from both piles. The player who takes the last token is the winner.

It turns out that the Sprague–Grundy function for this simple game behaves quite chaotically.

In this talk we will present two new results on Wythoff's Grundy function $G$. The first one is a proof that for every integer $g \ge 0$, the $g$-values of $G$ are within a bounded distance to their corresponding 0-values. Since the 0-values are located roughly along two diagonals, of slopes $\phi$ and $\phi^{-1}$, the $g$-values are contained within two strips of bounded width around those diagonals.

Our second result is a ``convergence" conjecture and an accompanying recursive algorithm. We will show that for every $g$ for which a certain conjecture is true, there exists a recursive algorithm for finding the $n$-th $g$-value in time $O(\log n)$. We will present experimental evidence in favor of our conjecture for small $g$. The talk will include a brief review of the Sprague–Grundy Theory.