A question about the minesweeper game

This is just out of curiosity. Suppose the game has $m \times n$ boxes for positive integers $m$ and $n$. How can we make the sum of the numbers on a finished game the most?

There are two extreme cases, i.e., no mine, or each box is a mine. In these extreme cases, no number is written. Thus the sum is $0$. So I think maybe there exists a maximum number for the sum.

Solution 1:

I'll prove that the maximum $M\geq 2mn-m-n$.

A way to compute the sum is putting a stick that joins every pair of consecutive squares such that one of them has mine and the other hasn't. The number of sticks is equal to the sum of the numbers.

In a checkered board there are no diagonal sticks, but there is every possible vertical and horizontal stick. In each row, there are $m-1$ sticks, and in each column there are $n-1$ sticks. This makes

$$m(n-1)+n(m-1)=2mn-m-n$$

EDIT: This is not the maximum, as I thought. Suppose that there is an odd number $n$ of rows. Fill odd rows with mines and leave blank the even ones. If there is more than one column, the blanks in the border are filled with $4$'s and the rest with $6$'s. This makes $$6(m-2)\frac{n-1}2+2\cdot4\cdot\frac{n-1}2=3mn-3m-2n+2$$ which is greater than the other bound except for very small values of $m$ and $n$ (one-row or one-column boards and such).

Solution 2:

I'll prove that the maximum $M \leq 3nm - 2n - 2m + 2$.

First, note that if we assign to a bomb the number of non-bomb neighbors, the total sum doubles. Thus, we can obtain a more symmetric problem, which will be useful in what follows. (We could also just show that swapping all blank tiles with bombs and vice versa does not change the sum.)

For what follows, values will refer to the value in this alternate formulation.

Let there be a bomb in the interior of the board with seven clear neighbors (and thus, zero or one bomb neighbors). Then one of the orthogonally-adjacent cells has four known clear neighbors and one known bomb neighbor. (If there is no neighboring bomb, then choose any orthogonally-adjacent tile; if the neighboring bomb is orthogonally adjacent, choose the clear cell directly opposite the bomb; if the neighboring bomb is diagonal, then choose either of the cells on the two opposite edges.)

Since that cell has 4 clear neighbors and 1 bomb neighbor, it has a maximum value of 4 (if on the interior), and 1 (if on the border). Adding a bomb to that cell will add one to the values of its clear neighbors and not decrease its own value.

The same argument applies to clear cells with seven neighboring bombs.

So we see that we may assume that interior cells have a maximum value of 6.

Similarly, we will show that, optimally, border cells do not attain a value of 5.

For if a bomb on the border has five clear neighbors, the neighbor opposite the border has four clear neighbors and one bomb neighbor; the same argument as above applies.

So we may assume that border cells have a maximum value of 4.

So an upper bound for the maximum sum (in the original problem) is \begin{align} M & \leq \frac{1}{2}\left(6(m-2)(n-2) + 4(2(m-2) + 2(n-2)) + 3\cdot 4 \right) \\ & = 3(m-2)(n-2) + 5(m-2) + 5(n-2) + 6 \\ & = 3mn - 2m - 2n + 2. \end{align} We've only shown this upper bound for when $m,n \geq 2$, but this bound happens to work for the $1\times n$ case, where it reduces to $n$, which is greater that the actual maximum of $n-1$.

Note that a pattern of stripes, as shown by user ajotaxte, produces a lower bound of $$M \geq 3mn - 3m - 2n + 2.$$

In conclusion, we see that the maximum for $m\times n$ grids, with $m \leq n$, is $$ 3mn - 3m - 2n + 2 \leq M \leq 3mn - 2m - 2n + 2.$$

Solution 3:

I will try to evaluate the total sum of numbers in the average.

Let $k$ be the total number of mines in a game. The probability that a tile contains a mine is $p = \frac{k}{mn}$. It has no mine with probability $q = 1-p$. Consider now a tile not on the border. It has $8$ neighbours tiles, and then:

$$\text{Pr}(X = x) = p^xq^{8-x}, x \in \{0, \ldots, 8\}$$

where $X$ represents the number present in the a tile. We can say that, when there is a mine, the $X$ is $0$, and hence:

$$\text{Pr}(X = x) = \left\{\begin{array}{ll} p + q \cdot q^8 & x = 0 \\ q \cdot p^xq^{8-x} & x \in \{1, \ldots, 8\} \end{array}\right. $$

The average number present in a tile is:

$$\mathbb{E}[X] = q\sum_{x=1}^8p^xq^{8-x} = q\left[\sum_{x=0}^8p^xq^{8-x} - p^0q^{8-0}\right] = $$ $$=q\left[1 - q^8\right] = q - q^9$$

Consider now a tile on a border but not in a vertex. It has $5$ neighbours.We have that:

$$\text{Pr}(X = x) = \left\{\begin{array}{ll} p + q \cdot q^5 & x = 0 \\ q \cdot p^xq^{5-x} & x \in \{1, \ldots, 5\} \end{array}\right. $$

and

$$\mathbb{E}[X] = q- q^6$$

Now we work on tiles on a vertex. It has $3$ neighbours.We have that:

$$\text{Pr}(X = x) = \left\{\begin{array}{ll} p + q \cdot q^3 & x = 0 \\ q \cdot p^xq^{3-x} & x \in \{1, \ldots, 3\} \end{array}\right. $$

and

$$\mathbb{E}[X] = q - q^4$$

There are $(m-1)(n-1)$ tiles of type $1$, $2(m-1)+2(n-1)$ tiles of type $2$ and $4$ tiles of type $3$. Then, the average sum is:

$$(m-1)(n-1)(q - q^9) + (2(m-1)+2(n-1))(q-q^6) + 4(q-q^4)$$