Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Of course the maximum exists. If you add a bomb to the board the sum will be changed by a value in $\{-8,\ldots,8\}$. So the maximum is less or equal than $8*\text{lengh}*\text{width}$. –  miracle173 May 24 at 9:48
    
For the $n*1$ board the maximum is $\lceil \frac{n}{2} \rceil$. –  miracle173 May 24 at 10:00
    
The maximum seems to be $2mn-m-n$. This value is easily reached with a, for example, checkered board. The hard part is to prove or disprove that it's actually the maximum. –  ajotatxe May 24 at 10:14
    
@miracle173 For the $n\times 1$ board the maximum is $n-1$. It can be attained alternating mines and no mines. –  ajotatxe May 24 at 10:28
    
@ajotatxe: you are right –  miracle173 May 24 at 10:44

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
1  
The checkerboard and the stripes should both be stable points: Every square has either a number or a bomb; removing a bomb does not increase the total (decreases in case of stripes, stays same in case of checkerboard); adding a bomb does not increase total (decreases in case of stripes, stay same in case of checkerboard). –  Neal May 24 at 11:38

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.