¿Cuál es el máximo número posible de elementos de $S$?

Question

Este es un problema interesante que he encontrado.

Vamos a no ser de 2 dígitos de la secuencia que puede comenzar con 0, como 04 o 93. Vamos a un "empujón" se define como exactamente una de las siguientes operaciones:

1) el Aumento de uno de los dígitos por 1.

2) la Disminución de uno de los dígitos por 1.

3) Cambio de 0 a 9.

4) el Cambio de un 9 a 0.

Por ejemplo, es posible codazos de 19 están 09, 29, 18, y 10.

Decir que $S$ es un conjunto de 2-dígitos secuencias para que tarda 3 o más codazos para transformar cualquier elemento de $S$ en algún otro elemento de $S$. ¿Cuál es el máximo número posible de elementos de $S$?

Pensé en un zumbido como el de un caballero que se mueve en un tablero de ajedrez, pero con un tablero de 10x10 numeran empezando con el 1 en la parte superior izquierda y 100 en la parte inferior derecha. Claramente el máximo es de $100-1=99$ codazos, pero que sin tomar en cuenta la condición adicional en la declaración del problema. Alguna idea de cómo continuar?

Answer 1

Su pensamiento de un tablero de ajedrez es una buena. Reglas de cada elemento que pones en $S$ $12$ otros. Parece caballero movimientos causan mucha superposición de cuadrados excluidos. Mi primer pensamiento sería $00,12,24,36,48,50,62,74,86,98,05,17,29,31,43,55,67,79,81,93$ $20$

Answer 2

El pensamiento de una $10\times10$ tablero de ajedrez es bueno - no olvide que usted tiene que imaginar la parte superior y los lados de la parte inferior como se adyacentes, como también los lados izquierdo y derecho. Para cualquier par de $p=(x,y)$$S$, definir el barrio de $p$ a ser el conjunto de todos los pares que se puede llegar en más de un codazo de $p$. Es decir, el barrio es $$\{\,(x,y),\,(x+1,y),\,(x-1,y),\,(x,y+1),\,(x,y-1)\}\ ,$$ donde interpretamos $0-1$$9$$9+1$$0$. No es difícil ver que

se tarda $3$ o más codazos para transformar $p$ $q$si y sólo si los barrios de $p$ $q$ no se superponen.

Teniendo en cuenta que cada barrio tiene el tamaño de $5$, vemos que no hay más de $20$ barrios puede encajar en el $100$ disponibilidad de plazas sin que se superpongan. Sin embargo, esto no garantiza que el $20$ son posible: tenemos que considerar su "forma", así como su "tamaño". Pero no es demasiado difícil encontrar una solución por ensayo y error: los diferentes colores indican los barrios, y los "centros" de los barrios son los elementos de $S$. $$\def\b{\!\color{blue}{\blacksquare}\!} \def\r{\!\color{red}{\blacksquare}\!} \def\y{\!\color{amarillo}{\blacksquare}\!} \def\g{\!\color{verde}{\blacksquare}\!} \begin{matrix} \b&\r&\g&\g&\g&\r&\b&\y&\y&\y\\ \r&\r&\r&\g&\y&\b&\b&\b&\y&\g\\ \g&\r&\b&\y&\y&\y&\b&\r&\g&\g\\ \y&\b&\b&\b&\y&\g&\r&\r&\r&\g\\ \y&\y&\b&\r&\g&\g&\g&\r&\b&\y\\ \y&\g&\r&\r&\r&\g&\y&\b&\b&\b\\ \g&\g&\g&\r&\b&\y&\y&\y&\b&\r\\ \r&\g&\y&\b&\b&\b&\y&\g&\r&\r\\ \b&\y&\y&\y&\b&\r&\g&\g&\g&\r\\ \b&\b&\y&\g&\r&\r&\r&\g&\y&\b\\ \end{de la matriz}$$