[Math] A question about the minesweeper game

combinatoricsgraph theory

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?

enter image description here

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.

Best Answer

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).

Related Question