Rompecabezas: Descifrando la caja fuerte

Question

Una caja fuerte está protegida por una combinación de cuatro dígitos $(0-9)$. La caja fuerte solo considera los últimos cuatro dígitos ingresados ​​cuando decide si una entrada coincide con el código de acceso.

Por ejemplo, si ingreso la secuencia $012345$, estoy probando cada una de las combinaciones $0123$, $1234$ y $2345$.

Claramente, una cadena de longitud 40000 $000000010002...9999$ está garantizada para abrir la caja fuerte.

¿Podemos probar cada una de las 10000 combinaciones usando una cadena más corta? ¿Cuál es la cadena más corta que podemos idear para probar cada combinación?

Answer 1

El objeto en el que estás interesado se llama grafo De Bruijn. Construye un grafo donde cada nodo es una secuencia de 4 dígitos. Luego, coloca una arista dirigida de $a$ a $b$ si los últimos $3$ dígitos de $a$ son iguales a los primeros $3$ dígitos de $b.

Ver: http://en.wikipedia.org/wiki/De_Bruijn_graph

Un camino de Hamilton dirigido te indicará qué secuencia ingresar los dígitos (para probar todas las combinaciones posibles lo más rápido posible). Estos grafos siempre tienen dicho camino. Entonces, la menor cantidad de veces que tendrías que presionar el botón es $4$ (para el primer código) y luego $1$ pulsación más de botón por cada posibilidad restante para un total de $1(4)+9999(1)=10003$ pulsaciones de botón.

Answer 2

Puedes hacerlo con $10,003$ letras, y creo que esta es la cadena más corta posible. Comenzamos creando una secuencia de De Bruijn de las palabras de $4$ letras sobre el alfabeto $\{0,1,\dots,9\}$. Lo que es es una secuencia cíclica (lo que significa que cuando llegas al final, comienzas a leer desde el principio otra vez) que contiene cada palabra posible de $4$ letras exactamente una vez.

Veamos un ejemplo más corto para mayor claridad: consideremos palabras binarias de longitud $3$. Entonces afirmo que $$ 00010111 $$ es un ciclo De Bruijn para estas palabras, ya que al leer de izquierda a derecha obtenemos $$ 000,001,010,101,011,111,110,100. $$ Nota que entre $111$ y $110$ comenzamos a leer nuevamente al principio de la secuencia ya que es un ciclo.

Lo que De Bruijn demostró fue que, dado cualquier alfabeto $A$, siempre se puede crear tal ciclo para palabras de $n$ letras sobre $A$. Si lo pensamos como un ciclo, entonces tendrá una longitud de $|A|^n$, ya que cada letra inicia una palabra única de $n$ letras.

Volviendo a tu problema, podemos crear un ciclo De Bruijn para todas las cadenas de $4$ letras sobre $\{0,1,\dots,9\}$. Esto tendrá una longitud de $10,000$, pero no podemos ingresar un ciclo en la máquina, tenemos que ingresar una cadena. Por lo tanto, repetir las tres primeras letras al final de nuestra secuencia nos dará una cadena universal de longitud $10,003$.