Una pregunta sobre el juego del buscaminas

Question

Esto es sólo por curiosidad. Supongamos que el juego tiene $m \times n$ casillas para números enteros positivos $m$ y $n$ . ¿Cómo podemos hacer que la suma de los números de un juego terminado sea la más?

Hay dos casos extremos, es decir, que no haya ninguna mina, o que cada casilla sea una mina. En estos casos extremos, no se escribe ningún número. Por lo tanto, la suma es $0$ . Así que creo que tal vez exista un número máximo para la suma.

Answer 1

Voy a demostrar que el máximo $M\geq 2mn-m-n$ .

Una forma de calcular la suma es poner un palo que una cada par de cuadrados consecutivos de forma que uno de ellos tenga el mío y el otro no. El número de palos es igual a la suma de los números.

En un tablero de cuadros no hay palos diagonales, pero sí hay todos los palos verticales y horizontales posibles. En cada fila, hay $m-1$ palos, y en cada columna hay $n-1$ palos. Esto hace que

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

EDIT: Esto no es el máximo, como yo pensaba. Supongamos que hay un número impar $n$ de filas. Rellena las filas Impares con minas y deja en blanco las pares. Si hay más de una columna, los espacios en blanco del borde se rellenan con $4$ y el resto con $6$ 's. Esto hace que $$6(m-2)\frac{n-1}2+2\cdot4\cdot\frac{n-1}2=3mn-3m-2n+2$$ que es mayor que el otro límite, excepto para valores muy pequeños de $m$ y $n$ (tableros de una fila o de una columna y demás).

Answer 2

Voy a demostrar que el máximo $M \leq 3nm - 2n - 2m + 2$ .

En primer lugar, hay que tener en cuenta que si asignamos a una bomba el número de vecinos que no lo son, la suma total se duplica. Así, podemos obtener un problema más simétrico, que será útil en lo que sigue. (También podríamos mostrar simplemente que cambiar todas las fichas vacías por bombas y viceversa no cambia la suma).

Por lo que sigue, valores se referirá al valor en esta formulación alternativa.

Que haya una bomba en el interior del tablero con siete vecinos claros (y por lo tanto, cero o uno vecinos de la bomba). Entonces una de las casillas ortogonalmente adyacentes tiene cuatro vecinos claros conocidos y un vecino de bomba conocido. (Si no hay bomba vecina, entonces elige cualquier casilla ortogonalmente adyacente; si la bomba vecina es ortogonalmente adyacente, elige la casilla clara directamente opuesta a la bomba; si la bomba vecina es diagonal, entonces elige cualquiera de las casillas de los dos bordes opuestos).

Como esa celda tiene 4 vecinos claros y 1 vecino bomba, tiene un valor máximo de 4 (si está en el interior), y de 1 (si está en la frontera). Si se añade una bomba a esa casilla, se añadirá uno a los valores de sus vecinos claros y no se reducirá su propio valor.

El mismo argumento se aplica a las células claras con siete bombas vecinas.

Así, vemos que podemos suponer que las celdas interiores tienen un valor máximo de 6.

Del mismo modo, demostraremos que, de forma óptima, las celdas fronterizas no alcanzan un valor de 5.

Pues si una bomba en la frontera tiene cinco vecinos claros, el vecino de enfrente tiene cuatro vecinos claros y un vecino bomba; se aplica el mismo argumento anterior.

Por lo tanto, podemos suponer que las celdas fronterizas tienen un valor máximo de 4.

Así que un límite superior para la suma máxima (en el problema original) es \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} Sólo hemos mostrado este límite superior para cuando $m,n \geq 2$ pero resulta que este vínculo funciona para el $1\times n$ donde se reduce a $n$ que es mayor que el máximo real de $n-1$ .

Obsérvese que un patrón de rayas, como el mostrado por el usuario ajotaxte, produce un límite inferior de $$M \geq 3mn - 3m - 2n + 2.$$

En conclusión, vemos que el máximo para $m\times n$ rejillas, con $m \leq n$ es $$ 3mn - 3m - 2n + 2 \leq M \leq 3mn - 2m - 2n + 2.$$

Answer 3

Intentaré evaluar la suma total de números en la media.

Dejemos que $k$ sea el número total de minas en una partida. La probabilidad de que una ficha contenga una mina es $p = \frac{k}{mn}$ . No tiene ninguna mina con probabilidad $q = 1-p$ . Considere ahora un azulejo no en la frontera . Tiene $8$ azulejos de los vecinos, y luego:

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

donde $X$ representa el número presente en la baldosa a. Podemos decir que, cuando hay una mina, el $X$ es $0$ y por lo tanto:

$$\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. $$

El número medio presente en una baldosa es:

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

Considere ahora un azulejo en un borde pero no en un vértice . Tiene $5$ vecinos. Lo tenemos:

$$\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. $$

y

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

Ahora trabajamos en los azulejos en un vértice . Tiene $3$ vecinos. Lo tenemos:

$$\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. $$

y

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

Hay $(m-1)(n-1)$ baldosas de tipo $1$ , $2(m-1)+2(n-1)$ baldosas de tipo $2$ y $4$ baldosas de tipo $3$ . Entonces, la suma media es:

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