In cookie clicker there is a farming mini game. You can place plants on a grid. To unlock new plants, you have to place 2 plants you already have and on places adjacent to them (3x3 grid) there is a chance a new plant will mutate. We can model the garden as a matrix with elements being either 0 or 1 (or maybe 0, 1, 2, in case we try to mutate different types of plants): \begin{bmatrix}0&1&0\\0&1&0\\0&1&0\end{bmatrix} Here, in places of zeros there is a $p$% chance that a new type of plant will appear. The total chance that a new type of plant will appear can be calculated with Bernoulli trials: $1 - (1-\frac{p}{100})^k$, $k$ being the number of zeros.
How to find an optimal setup for an $n \times m$ garden, maximizing the chance of a new mutation appearing, without using brute-force?
I'd appreciate any theorems, literature and so on to learn more about it.
Some optimal examples:
You can solve the problem via integer linear programming as follows. Let $N_{ij}$ denote the set of neighbors of cell $(i,j)$. Let binary decision variable $x_{ij}$ indicate whether there is a plant at cell $(i,j)$. Let binary decision variable $y_{ij}$ indicate whether cell $(i,j)$ is empty and has at least two neighboring plants. The problem is to maximize $\sum_{i,j} y_{ij}$ subject to linear constraints \begin{align} y_{ij} &\le 1 - x_{ij} &&\text{for all $i$ and $j$} \tag1\label1 \\ 2 y_{ij} &\le \sum_{(k,\ell)\in N_{ij}} x_{k\ell} &&\text{for all $i$ and $j$} \tag2\label2 \end{align} Constraint \eqref{1} forces cell $(i,j)$ to be empty if $y_{ij}=1$. Constraint \eqref{2} forces at least two neighboring plants if $y_{ij}=1$.
For $n\times n$ grids with $n\in\{1,\dots,15\}$, I get the following maximum values: $$0,2,6,10,17,26,34,46,60,72,89,108,125,146,170$$