Permítanme empezar por la introducción de la exacta fórmula de recursión.
Definir $n \text{ pmod } 9$ como la única $r \in \{1, \cdots, 9\}$ tal que $n \equiv r \text{ (mod 9)}$. Ahora vamos a $R_0 = 0$, $F_0 = 10$ y
$$ R_{n+1} = (F_n + R_n) \text{ pmod }9, \qquad
F_{n+1} = \frac{10}{9}F_n + \frac{R_n - R_{n+1}}{9}. \etiqueta{1} $$
A continuación, $F_n$ es el número de indicadores utilizados en el $n$-ésimo día. Así
$$ F_0 = 10, \quad F_1 = 11, \quad F_2 = 12, \quad F_3 = 13, \quad F_4 = 15, \quad \cdots. $$
Primero vamos a entretener a la consecuencia de $\text{(1)}$.
Debido a de la $\text{pmod}$ operación $\text{(1)}$, parece muy desalentador para producir un simple y fórmula exacta para $F_n$ a pesar de que hace el cálculo un poco más fácil. Pero, sorprendentemente, nos puede dar una fórmula aproximada. La siguiente proposición resume algunas de las consecuencias.
La proposición. Deje $(R_n, F_n)$ ser definido por $\text{(1)}$. Entonces existe una constante $c > 0$ tal que
$$\left| F_n - c\left(\tfrac{10}{9}\right)^n \right| \leq \tfrac{8}{10} \tag{2} $$
para todos los $n \geq 0$. Más precisamente, tenemos la fórmula
$$ c = F_0 - \tfrac{1}{90} \sum_{k=1}^{\infty} \left(\tfrac{9}{10}\right)^k R_k. \tag{3} $$
Tanto en $\text{(2)}$ $\text{(3)}$ fácilmente sigue señalando que $ c_n = (\frac{9}{10})^n F_n$ satisface
$$c_{n+1} - c_n = \tfrac{1}{10}(\tfrac{9}{10})^n R_n - \tfrac{1}{9}(\tfrac{9}{10})^{n+1} R_{n+1} $$
y $R_n \in \{1, \cdots, 9\}$ todos los $n \geq 1$. A continuación, mediante el uso de $F_0 = 10$, hemos enlazado
$$ 9.1
= F_0 - \tfrac{1}{90} \sum_{k=1}^{\infty} \left(\tfrac{9}{10}\right)^k 9
\leq c
\leq F_0
= 10. $$
A partir de este y $\text{(2)}$, nos encontramos con que $ F_{21} \leq 92$$ F_{23} \geq 102$. Este cálculo también justifica por qué la aproximación $F_n \approx F_0 (\frac{10}{9})^n$ da una buena adivinar la respuesta real. Finalmente, este argumento puede ser refinado mediante el uso de los valores
$$(R_1, \cdots\ R_7) = (1, 3, 6, 1, 7, 5, 5), $$
de donde se desprende que el $c \leq 9.75725676$ y, por tanto,$F_{22} \leq 99$. Por lo $n = 23$ es la solución.
El siguiente es el valor aproximado de $c$ obtenido a partir de $F_{1000}$.
$$c \approx 9.567894269669703072501237496424161411067649282(4) \tag{4} $$
(Los números entre paréntesis dígito se refiere al primer dígito cuyo valor es incierto.) Aunque calcular este valor requiere el conocimiento de $F_1, \cdots, F_{100}$, una vez que este valor es conocido entonces usted puede aproximar $F_n$ bastante bien para $n$ relativamente menor que $1000$. Por ejemplo, este valor junto con el $\text{(2)}$ demuestra que $F_{22} = 97$$F_{23} = 108$.
La prueba de $\text{(1)}$. En el $n$-ésimo día,
- $F_{n-1}$ indica el número de indicadores utilizados en el día anterior, y
- $R_{n-1}$ denota el número total de indicadores utilizados hasta el día anterior modulo $10$.
Ahora considere el $(R_{n-1}, F_{n-1})$ como un punto en el plano $\Bbb{R}^2$. El uso de una bandera se corresponde con el movimiento
$$(x, y) \to (x+1, y-1)$$
en el avión, lo que refleja el hecho de que el recuento total de uso de la bandera, se incrementa en 1 y el número de la bandera de las existencias disminuyeron en 1. Ahora, este movimiento va a ser afectados si no tenemos banderas de la izquierda, es decir, este movimiento no puede cruzar la $x$-eje. Esto sugiere que podemos interpretar el problema como el número de movimientos antes de llegar a una frontera en $\Bbb{R}^2$. Sin gratificante regla, esta frontera será el $x$-eje.
Por supuesto, tenemos que tomar la gratificante regla en consideración. Nos damos cuenta de esto por la modificación de la frontera de la siguiente manera:
\begin{align*}
B
&= \bigcup_{k=0}^{\infty} [10k, 10k+9] \times \{-k\} \\
&= \big( [0,9]\times\{0\} \big) \cup \big( [10,19]\times\{-1\} \big) \cup \big( [20,29] \times\{-2\} \big) \cup \cdots.
\end{align*}
En otras palabras, por cada 10 útiles bandera, somos recompensados con la reducción de la frontera por 1 unidad de modo que usted puede hacer un extra de mover.
Ahora la idea es reemplazar esta frontera $B$ por una más fácil de calcular uno con el mismo efecto. En efecto, considerar la línea de $L$ definido por $y = (9 - x)/10$. A continuación, para $(a, b) \in \Bbb{Z}^2$ por encima de la frontera de $B$, se puede comprobar que los siguientes son equivalentes:
El movimiento de partida en $(a, b)$ se detiene en $(s, t) \in \Bbb{Z}^2 \cap B$
Dos líneas de $y = b - (x-a)$ $L$ se cruza en el $(s', t') \in \Bbb{R}^2$ satisfacción $\lceil s' \rceil = s$$\lfloor t' \rfloor = t$.
La siguiente figura muestra el caso de $(a,b) = (2,12)$.
$\hspace{6em}$ ![pictorial demonstration of the equivalence]()
Aquí la negrita y de color rojo segmentos de línea que representan a $B$, mientras que la línea discontinua representa el $L$. Y las flechas azules representan los movimientos realizados, así como parte de la línea de $y = b - (x-a)$. Observe que esta línea intersecta $L$ en el half-open plaza de $S = (s-1, s]\times[t,t+1)$ exactamente cuando el movimiento se detiene en la esquina inferior derecha $(s,t)$ de los cuadrados de las $S$.
Ahora un simple álgebra muestra que $s = \lceil \frac{10}{9}(a + b)\rceil - 1$. A continuación, $s - a$ corresponde a el número de movimientos realizados en este día y $s \text{ mod } 10$ representa el número total de movimientos realizados hasta el día de hoy modulo 10. Aplicando esto a $(R_{n-1}, F_{n-1})$ y utilizando la siguiente observación
$$ \lceil \tfrac{10}{9}m \rceil - 1 = \tfrac{10}{9}m - \tfrac{1}{9}(m \text{ pmod } 9), \qquad \forall m \in \Bbb{Z} $$
produce $(R_n, F_n)$$\text{(1)}$, completando la prueba.
