Hitori y la conectividad de los gráficos

Question

Hitori es un juego parecido al Sudoku.

Estas son sus reglas:

1. Consiste en un $n\times n $ matriz. Sus términos son números enteros de $1$ a $n$ . Digamos que cada término está en un cuadrado.

2. El jugador debe marcar cada casilla como blanca o negra.

3. No hay dos blanco cuadrados en la misma fila o columna pueden tener el mismo número.

4. No hay dos negro las plazas pueden compartir un lado.

5. El conjunto de cuadrados blancos está conectado (dos cuadrados están conectados si comparten un lado).

6. La solución, es decir, la coloración de los cuadrados, es única.

Mi pregunta es sobre la proporción de cuadros negros . He jugado un buen número de partidas y esta proporción parece estar acotada en torno al 30%, pero no tengo los conocimientos necesarios para encontrar un buen límite preciso y demostrarlo. Me gustaría probarlo yo mismo .

El límite inferior parece estar relacionado con la tercera regla. Es decir, se marca un cuadrado como negro porque se sabe que otro cuadrado con el mismo número en la misma fila o columna es blanco. No hay ninguna otra razón para que un cuadrado sea negro.

El límite superior parece estar relacionado con las reglas 4ª, 5ª y 6ª. Es decir, se marca un cuadrado como blanco porque es adyacente a un cuadrado negro, porque al ser negro el conjunto de cuadrados blancos quedaría desconectado o simplemente porque no hay cuadrados blancos con el mismo número en la misma fila o columna.

Mis pensamientos hasta ahora : Los teoremas que he buscado sobre conectividad de grafos son sobre mínimo cortes para que el gráfico esté desconectado. Pero se trata de máximo cortes para que el gráfico esté conectado.

Por otro lado, para $n=3$ He encontrado estas tablas (0 es blanco y 1 es negro): $$\begin{bmatrix}1&0&0\\0&1&0\\0&0&0\end{bmatrix}$$ $$\begin{bmatrix}1&0&1\\0&0&0\\1&0&1\end{bmatrix}$$ Pero sospecho que los límites para la relación puede mejorarse como $n$ está aumentando .

Por lo tanto, mi pregunta es: ¿qué teoría de grafos debo estudiar para encontrar estos límites?

Answer 1

El límite inferior parece estar relacionado con la tercera regla. Es decir, se marca un cuadrado como negro porque se sabe que otro cuadrado con el mismo número en la misma fila o columna es blanco. No hay ninguna otra razón para que un cuadrado sea negro.

En realidad, la clave del límite inferior es la regla 6: la regla de la unicidad. Para ver esto, observe que cualquier solución en la que un cuadrado blanco no esté obligado a ser blanco debido a las reglas 4 o 5 no es una solución única, porque aparentemente puede hacerse negro sin violar ninguna de las reglas, y por lo tanto eso también sería una solución.

Así que sí, la regla 3 obligará a que haya casillas negras, pero la regla 6 es la que realmente te dirá cuántas negras debe haber como mínimo para que la solución sea única.

Por ejemplo, la regla 6 descarta definitivamente cualquier solución con un $3 \times 3$ región de todos los blancos, o bien podría hacer que el del medio fuera negro y tener otra solución: no crearía ninguna dos casillas negras adyacentes, y todas las casillas blancas se mantienen conectadas. También hay que tener en cuenta que la regla 6 descarta cualquier $1 \times 1$ Tablas Hitori, ya que hacer esa casilla blanca o negra constituiría una solución.

La forma de conseguir el mayor número de casillas blancas (y, por tanto, el menor número de casillas negras) sin obtener soluciones múltiples (es decir, sin poder hacer ninguna casilla negra más) es hacer que las casillas negras fuercen el mayor número posible de casillas blancas, y para ello se quiere utilizar el siguiente patrón general:

Tenga en cuenta que este patrón tiene cada negro no en el borde forzar su $4$ casillas vecinas a ser blancas (regla 4), mientras que no hay dos negras que obliguen a la misma casilla a ser blanca, lo que significa que no se puede conseguir una mayor proporción de blancas. La imagen siguiente lo ilustra: cada negra está en medio de una cruz suiza formada por $5$ cuadrados, que pueden utilizarse para embaldosar el tablero.

Si este fuera un tablero infinito, se obtendría un negro por cada $5$ cuadrados, por lo que el límite inferior absoluto es $20$ %.

Ahora bien, para los tableros finitos todavía hay algunas piezas de borde/esquina que no son obligadas a ser blancas por las negras. Para lo anterior $8 \times 8$ tablero cualquier solución real tendría que ser algo así:

Y ahora estás en $25$ %. Observo que tienes $2$ de $9$ para $n=3$ que es $22$ %.... por lo que sospecho que el límite inferior subirá y bajará ligeramente dependiendo del $n$ pero que tenderá a acercarse cada vez más a $20$ % como $n$ se hace cada vez más grande.

Para el límite superior, por supuesto se quiere hacer lo contrario: que los cuadrados blancos sean forzados por múltiples cuadrados negros. Por lo tanto, hay dos patrones de relleno básicos:

(todo blanco es forzado por $2$ negros)

y:

(la mitad de los blancos están obligados por $3$ negros, y la otra mitad por $1$ )

Para un tablero infinito que te lleva $1$ de $3$ cuadrados para ambos patrones, es decir $33.3$ %. Por supuesto, ninguna de estas dos son soluciones reales, ya que no todos los blancos están conectados, y por lo tanto para un tablero real tendrías que quitar algunos negros de nuevo, y obtendrías algo como:

o:

El segundo patrón parece funcionar un poco mejor... para esto $8 \times 8$ tablero, usted tiene $19$ de $64$ negros, es decir, casi $30$ %. Ahora, observo que para $n=3$ tienes $4$ cuadrados negros de $9$ es decir $44$ %, pero esta es realmente una situación excepcional. Para $n=4$ lo mejor que puedes hacer es $5$ cuadrados negros, y así con $5$ de $16$ estás por debajo $33.3$ % ... Para $n=5$ , puedes volver a $9$ de $25$ (es decir, un poco más de $33.3$ %), pero apuesto a que para cualquier $n$ no puedes superar $33.3$ %. Como $n$ se eleva cada vez más, sin embargo, el límite superior debería acercarse cada vez más a $33.3$ %

Ahora bien, probablemente se podría generar alguna fórmula exacta para $n$ (probablemente con funciones de techo y/o suelo) utilizando estos patrones, pero lo dejaré a tu criterio.