Date: Sunday, 23 Adar II 5765 (Apr. 3, '05)

Speaker: Gabriel Nivasch (Tel-Aviv University)

Title: "On the Sprague-Grundy function for Wythoff's game"

Abstract:
---------
The game of Wythoff is a simple combinatorial game for two
players. There are two piles of tokens, of sizes x, y >=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>=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.