Recursively color the board in white and black such that for any legal move, there is an odd number of black squares that are flipped.
In your case the coloring will look like an inverted serpinski pattern shifted diagonally :
Then consider the parity of the number of $1$s on black squares.
At every move you invert an odd number of black squares, so the parity changes no matter what the players do. The number of $1$s on black squares either increases by $1$ or decreases by $1$ or $3$.
In your example, there are $17$ $1$s on black squares, so player $1$ will always see an odd number of $1$s on black squares. $0$ is not odd so there will always be at least one $1$ on a black square. He can't possibly receive an empty board so he can't lose : he's forced to win.
I don't know what your website is doing. If some algorithms win more than others then either the rules are different (he never says what happens on the edges of the board) or he has an unfair way of generating random boards. Also I don't know what he does when he recalculates the scores.
Maybe this is just an experiment in feeding random results to an elo scoreboard.
The game you are considering is called a "Chip-Firing Game" in the literature, and variants of this game are fairly well studied. In particular, the problem you have posed (as well as several related problems) are solved in this paper (Chip Firing Games on Graphs - Bjorner, Lovasz, and Shor).
For ease of reference, I will paraphrase the proof below:
Let $G$ be a graph with $n$ vertices, $m$ edges, and $N$ chips assigned to its vertices.
In a step of the game, a vertex $v$ with more chips than its degree "fires" $deg_v$ many chips, one to each of its neighbors. The game ends when no vertex can fire.
Theorem (Bjorner, Lovasz, Shor):
- If $N > 2m-n$ the game is infinite
- If $m \leq N \leq 2m-n$ there exists initial configurations guaranteeing either a finite or an infinite game
- If $N < m$ then the game is finite
I will only summarize the proof of the last bullet - the rest is in the linked paper.
Let $f(v)$ denote the chips on node $v$. Consider an acyclic orientation of $G$, and let $T = \Sigma_v \max\{0, f(v) - \deg^+(v)\}$. This is the quantity we will show decreases.
Call a node $u$ deficient if $f(u) < \deg^+(u)$.
Since $N < m$, there must exist a deficient node. Consider the first $v$ that is fired. Clearly $f(v) \geq \deg(v)$. After firing, reverse the orientation of all edges leaving $v$. We do not create a cycle, and moreover we do not increase $T$.
Edit (clarification of why $T$ is nonincreasing):
Note the summand of $T$ corresponding to $v$ decreases by $\deg(v) - \deg^+(v)$. This is because we lose $\deg(v)$ many chips on $v$, but we are no longer subtracting the $\deg^+(v)$ many outgoing edges (since we flipped them). However, for each neighbor $u$ of $v$, if it was connected by an outgoing edge of $v \to u$, the $T$ summand of $u$ does not increase (since $f(u)$ and $\deg^+(u)$ both increase by $1$. If instead $u$ is among the $\deg(v) - \deg^+(v)$ vertices such that $u \to v$ is an edge, then the $T$ summand corresponding to $u$ increases by at most $1$.
Indeed if a node $u$ adjacent to $v$ is deficient, then $T$ decreases. If none of the adjacent vertices was deficient, then the set of deficient nodes did not change.
Thus $T$ decreases over time (since eventually nodes which used to be deficient will have to fire, and $T$ decreases each time this happens), and the game is finite.
A good example to play with to get comfortable with how the proof works is
the following graph:
I've fixed an initial orientation in advance, but you could do it with any (acyclic) orientation you please.
Of course, for your example we can take $G$ to be a cycle on $n$ vertices, and so $n=m$. The part of the theorem we just proved, then, says that if the number of coins $N$ is less than $n$, the game always terminates. As desired.
Thanks for the problem! Researching a solution led to a lot of cool places.
Hope this helped ^_^
Best Answer
$P(n)$ is simply the statement that if the game is played with $2n+1$ players, there is a survivor. HINT for (b): Consider the two players who are closest together when the leader says stop.