Supongamos que usted tiene una computadora con una contraseña de longitud $k$ en un alfabeto de $n$ letras. Usted puede escribir un arbitrarly palabra larga y el equipo intentará de todas las subpalabras de $k$ cartas consecutivas. ¿Cuál es la menor palabra que contiene todas las combinaciones de $k$ letras como subword? (es decir, la forma más rápida para hackear el ordenador :) )
La más pequeña palabra que contenga $n^k$ subpalabras de tamaño $k$ tiene una longitud de $k-1+n^k$ y con base en algunas casos, nos gustaría demostrar que de hecho, es posible encontrar una palabra de tal longitud que contiene todas las contraseñas posibles. El problema puede traducirse en un problema de teoría de grafos, tomando como vértices todas las palabras de longitud $k$.
Hemos intentado $k=2$, donde usted puede probar la conjetura por inducción. Para $n=2$ pequeñas y $k$ también funciona.
