La puerta que se abre sola

**Qué entrena:** cota inferior + construcción óptima (De Bruijn).

Hay una caja fuerte con código de 4 dígitos (0000 a 9999).

Puedes teclear una secuencia larga de dígitos. La caja se abre en cuanto los **4 últimos** dígitos tecleados coinciden con el código.

¿Cuántos dígitos necesitas teclear como mínimo para garantizar apertura, sin saber el código?

1. Cota inferior: Una cadena de longitud L contiene como máximo L-3 subcadenas distintas de longitud 4. Para cubrir los 10000 códigos: L-3ge 10000Rightarrow Lge 10003.
2. Cota superior (construcción): Existe una secuencia de De Bruijn B(10,4), cíclica, de longitud 10000, que contiene exactamente una vez cada bloque de 4 dígitos.
3. Al linealizarla y añadir los 3 primeros dígitos al final, obtienes una cadena de: 10000+3=10003 que cubre todos los códigos de 4 cifras.

[Volver al problema](#prob-caja-fuerte-de-bruijn-10003)

**Respuesta:** mínimo **10003** dígitos.

**Cota inferior:**
Una cadena de longitud $L$ contiene como máximo $L-3$ subcadenas distintas de longitud 4.
Para cubrir los 10000 códigos:
$$
L-3\ge 10000\Rightarrow L\ge 10003.
$$

**Cota superior (construcción):**
Existe una secuencia de De Bruijn $B(10,4)$, cíclica, de longitud 10000, que contiene exactamente una vez cada bloque de 4 dígitos.

Al linealizarla y añadir los 3 primeros dígitos al final, obtienes una cadena de:
$$
10000+3=10003
$$
que cubre todos los códigos de 4 cifras.

Como cota inferior y superior coinciden, el mínimo exacto es 10003.

---