Esto es realmente un problema de teoría de grafos. Aquí se explica cómo pensarlo. Para f (N) imagine un gráfico con nodos que representen cada N-tupla de dígitos. Habrá 10 ** N de ellos. Imagine que hay arcos dirigidos que conectan nodos cuyos números se superponen con N-1. Entonces, para N == 4, hay dos nodos etiquetados como 1234 y 2345, con un arco de 1234 a 2345. La forma de pensar en esto es cambiar el 1 y el 5. Así que hay 10 arcos saliendo de cada nodo , y si lo piensas, siempre hay 10 arcos entrando en cada nodo. Llamemos a esto G (N).
Desea encontrar la ruta más corta posible a través de este gráfico que toca cada nodo (al menos una vez). Eso le dará el valor para f (N).
Entonces, ¿cuánto dura eso? Si hay un ciclo hamiltoniano, solo se necesitan 10 * N pasos para recorrer cada nodo, sin duplicados, pero ¿cómo saber si existe dicho ciclo? La prueba va en dos pasos.
Primero, es una propiedad conocida de los gráficos uniformes en grados uniformes fuera de grado que existe un ciclo euleriano. Este es un camino cerrado a través del gráfico que cruza cada arco exactamente una vez. La prueba de esto se deja como un ejercicio para el lector, pero es fácil.
- ¿Qué es exactamente un algoritmo? ¿Qué califica como algoritmo?
- ¿Cómo resolver para f (n)? (n (n + 1)) ^ (ln f (n) / ln (n (n + 1)) = (n-1) / n) + f (n) ((n + 2) / 2)
- ¿Qué es f (n) = O (g (n))?
- ¿Por qué la construcción teórica de N tiene la función sucesora definida como s (n) = {n} U n y no solo {n}?
- ¿Cómo resolverías cos3x-cos2x = sin3x-sin2x?
En segundo lugar, este gráfico es lo que se llama un dígrafo de línea iterado, en el que se puede crear G (N + 1) a partir del gráfico para G (N) interpretando cada arco de G (N) como un nodo de G (N +1). En consecuencia, el ciclo euleriano conocido para G (N) se convierte en un ciclo hamiltoniano para G (N + 1).
Ahora casi hemos terminado. Hay una ruta cerrada en este gráfico que visita cada nodo exactamente en 10 ** N pasos, pero el número que solicita no está cerrado en un bucle, por lo que los últimos dígitos N-1 de la ruta deben duplicarse al principio , entonces la respuesta es f (N) = (10 ** N) + (N-1)
El lector astuto notará que estos argumentos no dependen del número 10 de ninguna manera, y de hecho el argumento funciona para cualquier base.
Estos gráficos son bien conocidos y se llaman gráficos de Bruijn y tienen muchas propiedades interesantes. Las secuencias sobre las que preguntaste se llaman secuencias de Bruijn. Hay gráficos relacionados llamados gráficos de Kautz que son como los gráficos de Bruijn, excepto que la secuencia de dígitos en f (N) no puede tener el mismo dígito dos veces seguidas.
Y finalmente, extrañamente, sé sobre estas cosas solo porque solía trabajar en una compañía de supercomputadoras llamada SiCortex, que usaba gráficos Kautz para conectar todos los procesadores.