'''Conway's Army Percolation'''

''Gabriel Istrate, Mihai Prunescu (Universitatea din Bucuresti)''


We study a probabilistic version of the celebrated Conway's Army game.
In this game the lower semiplane of an infinite chessboard is filled
with checker pieces. A celebrated result due to Conway (1961) shows
that one cannot move a checker piece in a finite number of steps to a
position on row 5 (rows 1-4 are reachable).

In the version that we are interested in, inspired by percolation
theory, we assign pieces to all cells of the lower semiplane
independently by flipping a coin with success probability $p$ (where
$p$ is a fixed constant between 0 and 1). We are interested in
estimating $D_{k}(p)$, the probability that one can reach a fixed cell
on line $k$, for $k=1,2,3,4$. We derive several results that provide
lower and upper bounds on this probability. These results show that
$0<D_k(p)<1$ for every $p\neq 0,1$, and suggest the fact that the
$D_{k}(p)$ is an analytical function of $p$.

We then explain why the problem we study can be regarded as a type of
percolation problem on hypergraphs. We also report on how to use SAT
solvers to study the problem experimentally.