Por qué la función "número autorreferencial" acaba fijando todos los puntos

Question

Dado un número decimal de 8 cifras $N$ , emite un nuevo número de 8 dígitos $f(N)$ cuyo primer dígito es el número de ceros en $N$ el segundo el número de unos, ..., el séptimo el número de seises, y el octavo el número de distinto dígitos de $N$ .

El MoMath publicó un acertijo que se reduce a "encontrar el punto fijo (único) de $f$ ", y la solución dada era empezar con un número de semilla arbitrario $N$ y aplicar $f$ hasta encontrar el punto fijo. Comentan por qué no hay ninguna razón a priori para que esto funcione, y admiten que no están seguros de por qué funciona. Aquí están mis preguntas relacionadas:

1. ¿Hay alguna manera de ver que $f$ tiene un único punto fijo?

2. ¿Hay alguna manera de ver que la aplicación $f$ a partir de cualquier semilla arbitraria $N$ se llega al punto fijo y no se entra en un ciclo al aplicar $f$ ?

3. Destacan que no importa qué semilla elijas, $f$ encuentra su punto fijo con relativa rapidez (por ejemplo, en $10$ aplicaciones de $f$ ). ¿Alguien tiene una razón para que se encuentre el punto fijo tan pronto? No sé muy bien cómo acotar la rapidez con la que esto ocurre.

Answer 1

Aún no es una respuesta completa pero aquí hay algunos comentarios, aún no bien ordenados.

1. Algo de fuerza bruta Estudiando todas las posibilidades, $[2,3,1,1,0,1,0,5]$ es el único punto fijo para $f$ .

No hay bucles, todo $10^8$ entradas posibles convergen a este valor, en como máximo 8 pasos . He aquí un histograma del número de iteraciones necesarias

Con datos : \begin{array}{c||c} \text{Nb of iterations} &\text{ Nb of inputs}\\ \hline 0&1\\ 1&3359\\ 2&1407840\\ 3&4939200\\ 4&17522400\\ 5&40745460\\ 6&25723446\\ 7&7367026\\ 8&2291268\\ \end{array} Y $[0, 0, 0, 0, 7, 7, 8, 9]$ es un ejemplo de entrada que necesita 8 iteraciones. Aquí está el "camino" hacia el punto fijo, esperaba usar esto para buscar alguna variante invariante o monótona pero no pude encontrar ningún patrón. \begin{array}{c||c} \text{step}&\text{value}\\ \hline 0&[0, 0, 0, 0, 7, 7, 8, 9]\\ 1&[4, 0, 0, 0, 0, 0, 0, 4]\\ 2&[6, 0, 0, 0, 2, 0, 0, 2]\\ 3&[5, 0, 2, 0, 0, 0, 1, 3]\\ 4&[4, 1, 1, 1, 0, 1, 0, 5]\\ 5&[2, 4, 0, 0, 1, 1, 0, 4]\\ 6&[3, 2, 1, 0, 2, 0, 0, 4]\\ 7&[3, 1, 2, 1, 1, 0, 0, 5]\\ 8&[2, 3, 1, 1, 0, 1, 0, 5] \end{array} 2. Algunas primeras reflexiones Sea $N=[a_0,a_1,\ldots,a_6,a_\#]$ sea un punto fijo para $f$ . Tenga en cuenta que

1. Debemos tener $$\sum_{i=0}^6 a_i \leq 8\qquad (*)$$
2. Dado que $[1,1,\ldots,1]$ no es un punto fijo, $a_\#>1$
3. Supongamos que $a_\#>5$ entonces $$\sum_{i=0}^6 a_i \geq 0+1+2+3+4 > 8$$ una contradicción. Por lo tanto $a_\#\leq 5$ .
4. Supongamos que existe algún $i\in \{0,\ldots,6\}$ tal que $a_i\geq 7$ . Entonces debemos tener al menos 7 veces el mismo número. Condición dada $(*)$ este número sólo puede ser 1, e implica que $a_\#=1$ una contradicción. Por lo tanto, para cualquier $i$ , $a_i\leq 6$ .
5. Esto significa que la desigualdad $(*)$ es de hecho una igualdad (contamos todo), $$\sum_{i=0}^6 a_i = 8\qquad (1)$$
6. Es complicado, pero también podemos demostrar que debemos tener $a_i< 4$ para cualquier $i\in\{0,\ldots,6\}$ . Estoy tratando de ver si puedo simplificar el argumento (pocos casos : si tenemos una $a_i=4$ entonces debemos tener $i=0$ o $i=1$ y ambos implican una contradicción, utilizando $a_\#\geq 2$ y $(1)$ ).