Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an unclaimed vertex (turning it blue) or a blue vertex, and similarly on his turn, Green adds a token to either an unclaimed vertex (turning it green) or a green vertex.

If a vertex of degree $d$ ever receives $d$ tokens, it topples, donating one token to each of its neighbors. This may in turn cause some of its neighbors to topple, and so on, as in the sandpile model. If Blue sets off a sequence of one or more topplings, she colors blue every vertex on which a token landed as a consequence of her move, and likewise for Green. (Note that because the sandpile model is abelian, we don't need to specify an order of topplings.) A player wins when she has managed to color the entire graph in her color.

Question: For which graphs $G$ is this game a first-player win?

I would be interested in any nontrivial statements for interesting classes of graphs, e.g., for paths, trees, cycles, complete bipartite graphs, grid graphs, whatever. The game is trivially a first-player win on a complete graph $K_n$: the first player simply plays $n - 1$ times on the same vertex, and there is nothing the second player can do. It's also not hard to see that it's a second-player win on the graph with two edges and three vertices: the first player cannot win on her move, and following her move there is always one token on the degree-2 vertex. The second player places a token on the unclaimed leaf vertex, which topples; there are now two tokens on the degree-2 vertex, which topples, making player 2 the winner.

Motivation: This came up not in my research but rather in my relaxation -- there's a game installed on my math department Linux distribution called KJumpingCube, which is precisely this game on square grid graphs.

One could also ask the same question for directed graphs, of course.

share|improve this question
    
Could you clarify what happens when tokens tumble on to vertices of the opposite color? In particular, do the opposing color tokens on that vertex disappear or remain? –  Joel David Hamkins Jul 2 '10 at 1:41
    
They remain. Tokens don't have color, just vertices; it is possible to set off an avalanche using primarily tokens that were on the other player's vertices at the beginning of your turn. –  JBL Jul 2 '10 at 1:52
    
Further clarification: When a vertex topples, it keeps its color? I ask this because I've also played a game like this on a square grid, but in that version, a toppled vertex became unclaimed again (might that make order matter? It had all possible topplings happen at once until there were none). I suppose it's necessary to have a vertex keep its color if winning condition is "color all vertices" and there are vertices of degree one (version I played just had "eliminate all opponent's vertices" as win condition). I suppose this verison is probably simpler... –  Harry Altman Jul 2 '10 at 4:31
    
Take the path with four vertices. If I understand the rules correctly, since placing a token at either of the degree-one ends causes that end to topple, after the first two moves you end up with one token in each of the degree-two vertices. The third move will cause an infinite chain toppling. I think you get similar results for longer paths. I wonder if the halting problem for this game is solvable. –  Doug Chatham Jul 2 '10 at 5:55
    
Well, if your infinite chain toppling covers the whole board - which it must, since the graph is connected - then I think we can just say you win. So that's not really a problem. –  Harry Altman Jul 2 '10 at 7:35

1 Answer 1

For an $n$-cycle, player 1 wins if $n$ is odd, else player 2 wins.

Since all vertices have degree 2, any vertex can have at most 1 token on it. Token-carrying vertices (of different colors) can be grouped into connected components. Call a component occupied by a player if it contains some vertex colored by the player, and that two components separated by a single vertex are adjacent. For example, the 6-cycle $(-\*-1-2-\*-1-\*-)$ has 2 components, the first occupied by both players, the second occupied by player 1, and they are adjacent.

Lemma: If less than $n-2$ tokens have been played, it is player $i$'s turn to play, and player $i$ occupies a component, then she can ensure that she continues to occupy a component until her next turn.

To do so, she simply topples a component occupied by her. Toppling an occupied component results in two adjacent components occupied by her (you can see this by working out the result of toppling an isolated component). These may merge with adjacent neighbors of the original component, but this does not affect her occupancy. The opponent can in her turn topple at most one of these two components, leaving the other still occupied.

Neither player can lose before $n-2$ tokens have been played, if both follow the above strategy. On the $(n-2)$th play, any move results in a single $(n-1)$-vertex component. Suppose $n$ is even, so that it is player 1's turn, and player 2 on the previous turn created two distinct components occupied by her as above. Whether player 1 topples one of the components if she also occupies it, or joins the two by playing on an empty vertex, it leads to a single connected component occupied by player 2. Player 2 then wins by toppling the final component on the $n$th move. The same argument holds for Player 1 if $n$ is odd.

The strategy as such does not necessarily work for paths, because toppling a component adjacent to an end of the path does not create two separate components. My hunch is that for even $n$, starting from the middle then playing as above may still be a winning strategy for player 1, as it avoids the ends till the last turn. I don't know what the right strategy is for odd $n$, though experimentation leads me to believe player 2 should win.

I also can't see if there's any way to generalize this for general graphs, because it depends crucially on there being at most one token per vertex.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.