Originators: Joel Brewster Lewis (graduate student MIT) (presented by Hannah Kolb - REGS 2010)
Definitions: Begin with a connected graph G, all vertices begin unclaimed and having score zero. Players Red and Blue take turns placing a token on a vertex. Red can place a token on an unclaimed vertex (making it red and giving it score 1) or on a red vertex, increasing the score of that vertex by 1. Blue follows the same rules, with "red" replaced by "blue".
When the score of a vertex equals its degree, it topples. The score of the toppled vertex v changes to 0 (it keeps its color), and the score of each vertex neighboring v increases by 1. This can cause a neighbor to topple, and the process continues as long as the score of any vertex is at least its degree. Each vertex reached during this process is claimed by the player who made the original placement. This is the only way for a player to claim a vertex that was held by the other player.
The game ends when all vertices have the same color. The player of this color wins.
Comments: When the total score exceeds the degree-sum minus the number of vertices, the toppling continues forever, but since the graph is connected this implies that one player has won.
On P2, Player 1 wins immediately. On P3, Player 2 wins on the second move of the game no matter what choices are made. However, on C3 either player could win, depending on what moves are made. On K1,m, Player 1 wins if m is odd, and Player 2 wins if m is even, no matter what moves are made.
Background: This game on a square grid can be found on Linux and is called KJumpingCube. A version of this idea by randomly placing tokens on a grid (also with toppling) has been studied in the Bak-Tang-Wiesenfeld [WTB] sandpile model (see also [L]).
Question 1: For which boards is there a predetermined winner, no matter what moves are played?
Question 2: For which boards does one of the players have a winning strategy?
Question 3: What can be said about the same game on directed graphs? Disconnected graphs?
Question 4: What is the smallest number of coins needed on a given graph to send it into an infinite topple? How is this achieved?
Comments: 2010 REGS participants have proved various results about this game.
References:
[L] J.B. Lewis,
Who wins this two-player game based on the sandpile model?
[WTB] Wiesenfeld, Kurt; Tang, Chao; Bak, Per A physicist's sandbox. Proceedings
of the Workshop on External Noise and Its Interaction with Spatial Degrees of
Freedom in Nonlinear Dissipative Systems (Los Alamos, NM, 1988). J. Statist.
Phys. 54 (1989), no. 5-6, 1441--1458.