Minecraft water spreading initial arrangements

So, as most Minecraft players quickly learn, the best way to flood an area is to place water along a diagonal. There are of course other ways to flood the same area with the same number of buckets placed.

For those not familiar with the game, we can think of this as a different sort of game. We start with a $0, 1$ matrix of size $n$. At each step, every $0$ with at least two $1$'s directly adjacent to it is replaced with a $1$. Its not hard to see that this process always terminates. The objective is to end with a matrix of all $1$'s with a minimal number of $1$'s to start.

Its not hard to see that an optimal initial arrangement is the identity matrix, and that the minimum number of starting $1$’s is $n$. Of course, there are other matrices that work, such as $$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}.$$

We quickly see that we are looking for permutation matrices, but not every permutation matrix works. For example $$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\end{pmatrix}$$ does not work.

The question then is this: which permutation matrices do work? Is there a nice characterization? We can think of forming "blocks" and then growing blocks together if they share a corner, but is there something else we can say? It appears the counter example given is some kind of forbidden configuration.

Edit: it appears that there are non-permutation matrices that work, such as $$\begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}.$$ Regardless, we can add the assumption that we are working only with permutation matrices. Thus we only consider expansion across corners as the other type of growth cannot happen.

Now if we consider starting with a permuation matrix, and grow it to its final state, we see that the final states are a bunch of disjoint squares of filled in area. We can shrink these squares to a single cell, so equivalently, we ask ourselves which permutation matrices exhibit no growth at all?

Solution 1:

Suppose we have a working permutation matrix $A$. Then it follows that there are two $1$'s in $A$ that are diagonally adjacent: $$ \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \quad \textrm{or} \quad \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}. $$ Let's say this occurs in rows $i$ and $i+1$ and columns $j$ and $j+1$. Note this could happen in many different places, so we just pick a single pair.

A small remark. For non-permutation matrices this need not happen. As written in the original post, there may be configurations where two $1$'s are in the same row or column with a single $0$ between them.

Now let's construct a new permutation matrix from $A$. The new matrix is obtained by replacing rows $i$ and $i+1$ with a single row of zeros and columns $j$ and $j+1$ with a single column zeros. We then set the entry in row $i$ and column $j$ of the new matrix to be $1$.

For example: $$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \mapsto \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $$ where the process is applied to the top left $2 \times 2$ corner of the matrix.

By assumption the original matrix $A$ works which means that this new permutation matrix also works. And similarly we can find a pair of diagonally adjacent $1$ in the new matrix. Doing this process inductively we eventually get the matrix $(1)$.

So it follows that if you want to construct all permutation matrices that work, then you can run this process in reverse.

I like to think of permutations in one-line notation: $(1,2, \dots ,n)$ for the identity etc. For permutations written in this form, we first find a pair of adjacent entries which have a difference of $1$. The process is to replace both of these entries with a single entry: their minimum $m$, and reduce by $1$ all values in the permutation which are greater than $m$.

So the above example is $(2,1,3) \mapsto (1,2)$. A longer example would be $$ (4,2,3,5,6,1) \mapsto (3,2,4,5,1) \mapsto (2,3,4,1) \mapsto (2,3,1) \mapsto (2,1) \mapsto (1) $$ where we are applying the process to the entries $(2,3), (3,2), (2,3), (2,3)$ and $(2,1)$.

Simiarly, running this process in reverse gives all possible permutations that work. This gives rise to an inductive classification of these permutations, i.e. the permutations of length $n$ that work are obtained from the permutations of length $n-1$. And conversely a permutation does not work if, after possibly applying the above process a few times, you reach a dead end thatis not $(1)$. The permutations $(a_1, \dots, a_n)$ is a dead end if $|a_i - a_{i+1}| \ge 2$ for all $i \in \{1, \dots, n-1 \}$.