Eraserhead (Games on Circles I)

This is not about the film by David Lynch. Eraserhead is played by two players on finite graph with some vertices occupied by erasers. At each turn, the player chooses one eraser, moves it to an unoccupied adjacent edge, thereby erasing the connecting edge. The player who moves last wins.

Let’s analyze this for cycle graphs.
Eraserhead1 01

If played with just one eraser, the first player chooses the direction, and all other moves are forced, until the eraser has erased all edges. So the first player wins if the cycle graph has an odd number of vertices. That was boring.

For two erasers, it gets slightly more interesting, but the outcome is the same: The first player can win if the number of vertices is odd. The two erasers divide the graph into two components whose number of vertices have different parity (3 and 4 in the example below).
Moving an eraser into the even component would be a mistake, as the second player will then move into the same component with the other eraser. This leaves an even number of moves for both players, and the second player will win.

But a winning move for the first player consists of moving one eraser into the odd component. This leaves the second player with two choices: Moving the other eraser either way leaves an odd number of moves for both players, and the first player wins. If the second player moves the first eraser again, the first player can move either way and will win.

Eraserhead2 01

So while a little harder, this was still easy. Does this even/odd pattern for winning and losing persist with more erasers? At first, it seems so. For any number of erasers (except the cases of no erasers and erasers everywhere, which leave no moves to begin with), the first (resp. second) player can always win with if the cycle graph has an odd (resp. even) number of vertices — up to cycle graphs with 8 vertices. For the following position with three erasers, the first player has no winning move. There are three essentially different moves, and the diagram give winning responses for the second player.

Eraserhead3 01

The first line is interesting. With the first player to move again, there are still 8 edges to delete (possibly). If the first player moves with the topmost eraser right, this will actually happen, and the first player will loose. To prevent this, s(he) must move that eraser to the left. This leaves all erasers in one component with a total of four edges left. This looks like a good thing, but no matter how they play, only three edges will be deleted, and the second player must win.

So the game does get complicated. What helps is to know the nimbers for simple subpositions, like chains with or without erasers at the end. For instance, the line graph with n vertices and one eraser at the end has nimber 1 for odd even n and 0 for odd n. Similarly, the line graph with n vertices and erasers at both end has nimber 0 for odd even n and 1 for odd n. This is quite trivial, of course, as all moves are forced. More surprisingly, for the line graph with two erasers at the end and a third eraser in between, the nimbers are again 1 for n odd, and 0 for n even, except when n=3 or n=4. Then the nimbers are 0 and 2, respectively. So things start off with promising simple patterns, but then deviate. Below I have, for line graphs of length 12 and 13, respectively a unit cube at coordinate (x,y,z) if the position with erasers at x, y, and z is a lost position for the first player.

Lost12 13

Finally, below, the corresponding images for cycle graphs, viewed diagonally to emphasize the symmetry. The discrepancy is baffling.

Lostcycle3 12

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s