Cuántos $10\times 10$ mesas podemos hacer?

Question

Cada celda de un $10 \times 10$ se rellena con un número entero no negativo, dos números de esta tabla se llaman adyacentes siempre que las celdas que los contienen tengan un lado común. Estamos buscando una tabla que tenga estas dos características siguientes:

A) la diferencia de cada dos números adyacentes debe ser $0$ o $1$ .

B) si un número es menor o igual que todos los números adyacentes, En este caso, debe ser $0$ .

¿Cuántas de estas mesas podemos hacer?

Utilizando la primera condición (A) he demostrado que debe haber un entero que repita al menos $10$ veces en la tabla , pero no he conseguido aplicar la segunda condición de forma que me lleve a la solución.

Se agradece cualquier ayuda, ¡gracias!

Answer 1

La disposición está determinada por el conjunto de fichas con ceros $A$ .

Consigue ese azulejo $x$ debe tener color $d(x,A)$ donde $d(x,A)$ es el número mínimo de veces que debes moverte a lo largo de fichas adyacentes para llegar a una ficha con un cero.

Primero hay que tener en cuenta que el número es como máximo $d(x,A)$ porque, de lo contrario, se puede buscar un camino de longitud mínima para $A$ y al menos una de las diferencias es mayor que $1$ .

Sea el conjunto de fichas con números menores que $d(x,A)$ sea $Y$ . Tome $y\in Y$ con el valor más pequeño escrito en él. Claramente $y$ tiene un valor menor o igual que sus vecinos en $Y$ por definición. Y también tiene un valor menor o igual que sus vecinos que no están en $Y$ ya que su distancia a $A$ es como máximo $d(y,A)-1$ . A continuación $y$ condición de las sasfías $2$ Así que $d(y)=0$ Así que $y$ está en $A$ , lo cual es una contradicción.

Concluimos que todo debe tener etiqueta $d(x,A)$ .

Por último, hay que tener en cuenta que ambas condiciones funcionan siempre con este etiquetado para cualquier $A$ .

Hay $2^{100}-1$ opciones para $A$ ( Obsérvese que debe haber al menos un cero, ya que de lo contrario un azulejo con etiqueta mínima viola la segunda condición).