Una caja fuerte parece exigir una larga lista de intentos separados. Pero si la cerradura lee siempre los últimos dígitos escritos, una sola secuencia puede esconder todas las claves posibles. Esa es la idea detrás de las secuencias de De Bruijn: ordenar combinaciones para que se solapen sin desperdiciar casi nada.
La puerta que se abre sola
Enunciado
Una caja fuerte usa un código de 4 dígitos, del 0000 al 9999.
Puedes teclear tantos dígitos como quieras, uno detrás de otro. La caja se abre en cuanto los cuatro últimos dígitos tecleados coinciden con el código correcto.
¿Cuál es la longitud mínima de una secuencia que garantice abrir la caja, sea cual sea el código?
Ver solución
Solución
Respuesta: mínimo 10003 dígitos.
La clave no es probar códigos separados, sino aprovechar que la caja mira siempre los cuatro últimos dígitos escritos.
Por ejemplo, si escribes:
no has probado una sola clave. Has probado todos los bloques de cuatro dígitos que aparecen seguidos:
Cada dígito nuevo, después de los tres primeros, crea una nueva clave posible.
Cota inferior:
Hay 10000 códigos posibles, desde 0000 hasta 9999. Una secuencia de longitud $L$ contiene como máximo $L - 3$ bloques consecutivos de 4 dígitos. Por tanto:
Luego:
Así que ninguna secuencia de menos de 10003 dígitos puede garantizar la apertura.
Por qué esa longitud sí basta:
Veamos primero una versión diminuta. Supón que solo existieran los dígitos 0 y 1, y que la clave tuviera 2 dígitos. Las claves posibles serían:
La secuencia
las contiene todas como bloques consecutivos de 2 dígitos:
No hemos escrito las claves por separado: las hemos solapado.
En la caja real ocurre lo mismo, pero con códigos de 4 dígitos y diez símbolos posibles.
Podemos imaginar cada terminación de tres dígitos como una estación. Por ejemplo, si estamos en la estación 314 y escribimos un 7, acabamos de probar la clave 3147 y pasamos a la estación 147:
Así, cada código de 4 dígitos es un camino entre dos estaciones de 3 dígitos.
De cada estación salen exactamente 10 caminos, uno por cada dígito que podemos añadir. Y a cada estación entran también exactamente 10 caminos, uno por cada posible dígito anterior.
Además, todas las estaciones están comunicadas: desde cualquier terminación de tres dígitos puedes llegar a cualquier otra escribiendo sus tres dígitos. Como cada estación tiene tantas entradas como salidas, existe una ruta cerrada que recorre cada camino exactamente una vez.
Al leer los dígitos de esa ruta, obtenemos una secuencia cíclica que contiene exactamente una vez cada bloque de 4 dígitos.
Esa secuencia cíclica tiene 10000 dígitos. Para convertirla en una secuencia lineal, repetimos al final los 3 primeros dígitos, de modo que no se pierdan los bloques que cruzaban el punto de cierre:
Como la cota inferior y la construcción coinciden, el mínimo exacto es: