Una función sobre los enteros y sus puntos fijos

Question

Definir $f:\mathbb{N}\rightarrow\mathbb{N}$ de la siguiente manera, $f(n)$ es el número de veces que se necesita el dígito "1" si escribiéramos todos los enteros entre 1 y $n$ (inclusive) en base 10. Así, por ejemplo

$f(1)=1$

$f(2)=1$

$f(3)=1$

...

$f(9)=1$

$f(10)=2$

$f(11)=4$

$f(12)=5$

...

$f(99)=20$ y así sucesivamente. Claramente $f(1)=1$ es un punto fijo. La pregunta original era encontrar el siguiente punto fijo. Inmediatamente establecí la relación recursiva

$$f(10^k-1)=10\cdot f(10^{k-1}-1)+10^{k-1}$$

con $f(9)=1$ . Entonces obtuve la relación explícita

$$f(10^k-1)=k\cdot 10^{k-1}.$$

Así que vemos que después de $n=1$ , $f(n)<n$ hasta llegar a $f(9,999,999,999)=10,000,000,000$ por lo que el punto fijo debe estar entre mil y diez mil millones. Entonces, después de contar cuidadosamente y de no perder de vista lo que estaba haciendo, obtuve que el punto fijo era

$$f(1,111,111,110)=1,111,111,110.$$

Ahora mis preguntas son

1. ¿Alguien sabe el origen de este problema? ¿Es un problema de Putnam/IMO/etc.? Escuché originalmente este problema hace mucho tiempo cuando empecé mi licenciatura y acabo de recordar al azar de nuevo hace unos días.

2. ¿Existe una forma elegante o más fácil de hacer esto de forma analítica?

3. Como no sé cómo me enteré de este problema... y es una pesadilla de recuperación de datos (como cuando intento buscar en Google), no tengo ni idea de si mi solución es correcta o no. ¿Alguien puede tal vez verificarla? No sé si me he equivocado al contar o no.

4. ¿Es posible codificar esto de manera eficiente para que pueda obtener una respuesta mediante una simulación? Por lo que recuerdo, probé con MATLAB y Mathematica, pero me llevó tanto tiempo que tuve que matarlos sin saber la respuesta y volver al papel y al lápiz. No probé C++ ni FORTRAN. En Mathematica intenté "optimizar" todo lo que pude usando sus funciones incorporadas pero era demasiado lento. En MATLAB, no pude ver cómo vectorizarlo así que sólo tuve que escribir un bucle que, por supuesto, es una mala idea. ¿Algún algoritmo eficiente? ¿Alguna idea?

5. Más bien una pregunta teórica, ¿hay alguna manera de probar que otro fijo después de $n=1$ incluso existe sobre $\mathbb{N}$ ? Utilizando la relación recursiva anterior vemos que

$f(999,999,999)=900,000,000$

y

$f(9,999,99,999)=10,000,000,000$

así que $f(n)>n$ y luego simplemente reduzco el intervalo hasta que obtengo $f(n)=n$ . Si consideramos la continuación suave de $f(x)$ en $\mathbb{R^+}$ entonces sí el teorema del valor intermedio nos garantiza el punto fijo ( $f(x)-x$ tiene un $x$ -intercepción porque cambia de signo). ¿Pero cómo sabemos, cómo podemos demostrar que el punto fijo está EXACTAMENTE en un número entero? Quiero decir que sé que la respuesta debe existir porque la pregunta fue planteada, pero francamente estoy un poco sorprendido de que haya otro número entero después de uno en el que el número entero es exactamente igual al número de veces que se necesita "1" para llegar allí.

6.¿Podemos decir algo sobre el comportamiento a largo plazo de $f$ ? Como la voluntad $f(n)$ sea siempre mayor que $n$ después del segundo punto fijo o oscilará yendo por encima y por debajo $n$ arbitrariamente muchas veces como $n$ tiende al infinito? ¿Existen otros puntos fijos? ¿Hay otros puntos fijos sobre los números naturales? ¿Hay alguna forma de encontrarlos todos? ¿La continuación suave de $f$ a los reales tiene una expresión de forma cerrada? ¿Cuál sería?

Gracias.

Answer 1

¡Qué pregunta tan larga!

Voy a responder a algunas de sus preguntas. Creo que ya he visto un problema similar a este en projecteuler. Como es más una web de programación, respondería a tu segunda pregunta diciendo que no hay una forma elegante de hacerlo... Pero como has visto, podemos tener fácilmente el valor de $f(10^k - 1)$ . En realidad, no es necesario hacer una recursión. Si lo piensas, $f(10^k - 1)$ es el número de números con $k$ dígitos o menos que tienen un $1$ en primera posición, más el número de los que tienen un $1$ en segunda posición, y así sucesivamente... Y el número de números con un máximo de $k$ dígitos, con un $1$ forzado en una posición, es $10^{k-1}$ (en otros lugares pones el dígito que quieras). Y lo haces $k$ veces por lo que se obtiene $f(10^k - 1) = k\cdot 10^{k-1}$ .

Nótese que no es tan obvio que el siguiente punto fijo esté entre mil y diez mil millones. De hecho, tiene

$f(99,999,999) = 80,000,000$ y $f(999,999,999) = 900,000,000$

pero podría tener por ejemplo $f(555,555,555) = 555,555,555$ ... Incluso parece poco probable, habría que probarlo.

Podrías comprobar que tu solución es efectivamente un punto fijo, y si lo es, es evidentemente el primero después de $1,000,000,000$ . Para hacerlo, haz con el mismo método que el que usé para $10^k - 1$ . En realidad, verás que el número de números $\leq 1,111,111,110$ que tienen un $1$ en $i$ -la posición es $111,111,111$ para cualquier $1\leq i \leq 10$ . Así que

$f(1,111,111,110) = 10\cdot111,111,111 = 1,111,111,110$

como quieras.

Además, se puede ver que para todos los $k \geq 100$ , $f(10^k-1) = k\cdot10^{k-1} \geq 10^{k+1} > 10^{k+1}-1$ . En consecuencia, no hay ningún punto fijo después de $10^{100}-1$ desde

$f(10^{100}-1) > 10^{101}-1$

$f(10^{101}-1) > 10^{102}-1$

y así sucesivamente, y $f$ es claramente creciente.

También te daré una idea para codificarla. Si buscas el primer punto fijo después de $n$ se hace una recursión como esta: Comienza con $n$ y calcular $f(n)$ con el método que mencioné (no es súper fácil de calcular pero es posible diferenciando algunos casos).

Si $f(n) = n$ has encontrado tu punto fijo.

Si $f(n) > n$ no hay ningún punto fijo antes de $m = f(n)$ Así pues, reinicie con $m$ .

Si $f(n) < n$ , calcule el menor número $m$ mayor que $n$ tal que $f(m) > n$ . Por ejemplo, si $n = 99$ , $f(99) = 20$ y sabe que su punto fijo tendrá un valor mayor que $99$ así que busca el número $m$ tal que $f(m) \geq 100$ . Y se reinicia con $m$ . No es fácil de codificar, pero creo que podría funcionar.

Por último, me parece un poco ambicioso hablar de una continuación suave de $f$ ... Las matemáticas no son tan bonitas :(

Espero que te sirva de ayuda ;)

Answer 2

Bueno, por si a alguien le interesa, después de investigar un poco he descubierto que el problema que publiqué, estaba en las entrevistas de trabajo de Google. A los aspirantes se les pedía que lo resolvieran en el momento (programando, supongo). También resulta que es una parte muy pequeña del problema #156 del Proyecto Euler. El enunciado del cual sugiere que esta función puede ser definida para cualquiera de los nueve dígitos no nulos. Para cada dígito tiene más de un punto fijo, pero sólo un número finito. Además, el mismo número puede ser un punto fijo para más de un dígito simultáneamente.

Además, la respuesta que encontré a mi problema era errónea. La respuesta aceptable en google... y el primer punto fijo después del 1 es en realidad 199981. Mi número es un punto fijo pero no el segundo más pequeño. Supongo que entonces no trabajaré en google ;-).