Encuentre la suma de todos los valores de $f ( 2017 )$ dado $f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ( a + b ) ^ 2$ .

Question

Dejemos que $f :\mathbb N \to \mathbb N$ sea una función inyectiva tal que $$f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ( a + b ) ^ 2$$ para todos $a , b \in \mathbb N$ . Sea $S$ sea la suma de todos los valores posibles de $f ( 2017 )$ . Encuentre $S \mod 1000$ . Aquí $$f ^ k ( n ) = \underbrace { f \Big( \dots f \big( f } _ { k \text{ times} } ( n ) \big) \dots \Big) \text .$$

Así que puse $a = b$ y descubrió que $f ^ { f ( a ) } ( a ) = f ( 2 a )$ .

Desde $f$ es inyectiva, $f ^ { f ( a ) - 1 } ( a ) = 2 a$ . Descubrí que $f ( 1 ) = 2$ .

Ahora $f ( 2 ) = 3$ poniendo el valor de $a = 1$ en la ecuación inicial y resolviendo para $f ( b ) = 3$ . Parece que al adivinar que $f ( n ) = n + 1$ ¿pero no puede la función ser periódica después de cierto intervalo y no tener límites y repetir su valor? Todavía puede ser inyectiva.

Answer 1

Es fácil ver que $f ( n ) = n + 1$ satisface la ecuación funcional $$f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ( a + b ) ^ 2 \text , \tag 0 \label 0$$ ya que entonces para cada entero positivo $m$ y $n$ se tendrá $f ^ m ( n ) = n + m$ . Se puede demostrar que ésta es la única solución inyectiva de \eqref {0} que mapea enteros positivos a enteros positivos, y por tanto el único valor posible para $f ( 2017 )$ es $2018$ que muestra $S = 2018$ y por lo tanto $S \mod 1000 = 18$ . Para ver esto, primero hay que tener en cuenta que $f$ no puede tomar el valor $1$ porque si $f ( n ) = 1$ para algún número entero positivo $n$ , dejando entonces que $a = b = n$ en \eqref {0}, se obtiene $f ( 2 n ) = 1$ que por la inyectividad de $f$ rinde $n = 2 n$ , lo que no puede ocurrir. A continuación, dejemos que $b = a$ en \eqref {0} para obtener $$f ^ { f ( a ) } ( a ) = f ( 2 a ) \text ,$$ y por inyectividad, $$f ^ { f ( a ) - 1 } ( a ) = 2 a \text , \tag 1 \label 1$$ como tú mismo has hecho. Podemos utilizar \eqref {1} para demostrar inductivamente $$f ^ { \sum _ { m = 1 } ^ n f \left( 2 ^ { m - 1 } a \right) - n } ( a ) = 2 ^ n a$$ para cada entero no negativo $n$ (tenga en cuenta que si $n = 0$ el lado izquierdo da $f ^ 0 ( a )$ es decir $a$ ), lo que demuestra, en particular, que $\left\{ f ^ i ( a ) \right\} _ { i = 0 } ^ \infty$ es infinito. Como consecuencia, podemos ver que si para algunos enteros no negativos $i$ y $j$ tenemos $f ^ i ( a ) = f ^ j ( a )$ , entonces debemos tener $i = j$ .

Ahora podemos demostrar que $f ( 1 ) = 2$ . Si ese no es el caso, debemos tener $f ( 1 ) = n + 2$ para algún número entero positivo $n$ . Entonces tenemos $f ^ { n + 1 } ( 1 ) = 2$ poniendo $a = 1$ en \eqref {1}, y dejando $a = f ^ n ( 1 )$ en \eqref {1} obtenemos $$2 f ^ n ( 1 ) = f ^ { f \left( f ^ n ( 1 ) \right) - 1 } \big( f ^ n ( 1 ) \big) = f ^ { f ^ { n + 1 } ( 1 ) - 1 } \big( f ^ n ( 1 ) \big) = f ^ { 2 - 1 } \big( f ^ n ( 1 ) \big) = f ^ { n + 1 } ( 1 ) = 2 \text .$$ Pero esto significa $f \left( f ^ { n - 1 } ( 1 ) \right) = 1$ , lo cual es imposible.

A continuación, demostramos que $f ( 2 ) = 3$ . Para ver esto, primero hay que notar que si para algún entero positivo $n$ y algún número entero positivo $k \ne 1$ tenemos $f ( n ) = 2 k$ , dejando que $a = k$ en \eqref {1} obtenemos $f ^ { f ( k ) - 1 } ( k ) = f ( n )$ y como debemos tener $f ( k ) > 2$ obtenemos $f \left( f ^ { f ( k ) - 3 } ( k ) \right) = f ( n )$ . Por la inyectividad de $f$ concluimos que existe un número entero positivo $m$ tal que $f ( m ) = n$ . Ya que al poner $a = 1$ y $b = 2$ en \eqref {0} y utilizando \eqref {1} tenemos $$f ( 3 ) ^ 2 = f ^ { f ( 1 ) } ( 2 ) f ^ { f ( 2 ) } ( 1 ) = f ^ 2 ( 2 ) f ^ { f ( 2 ) - 1 } \big( f ( 1 ) \big) = f ^ 2 ( 2 ) f ^ { f ( 2 ) - 1 } ( 2 ) = 4 f ^ 2 ( 2 ) \text ,$$ se deduce que hay un número entero positivo $k$ tal que $f ( 3 ) = 2 k$ . Como $f ( 3 ) \ne f ( 1 ) = 2$ Debemos tener $k \ne 1$ y, por tanto, hay un número entero positivo $m$ con $f ( m ) = 3$ . Sabemos que $m \ne 1$ . $m$ no puede ser igual a $3$ tampoco, porque entonces por \eqref {1} tendríamos $6 = f ^ { f ( 3 ) - 1 } ( 3 ) = f ^ 2 ( 3 ) = 3$ . Si $m > 3$ podemos dejar que $a = m - 3$ y $b = 3$ en \eqref {0} y ver que $$9 = f ( m ) ^ 2 = f ^ { f ( m - 3 ) } ( 3 ) f ^ { f ( 3 ) } ( m - 3 ) \text .$$ Como no de $f ^ { f ( m - 3 ) } ( 3 )$ y $f ^ { f ( 3 ) } ( m - 3 )$ puede ser igual a $1$ Debemos tener $f ^ { f ( m - 3 ) } ( 3 ) = f ^ { f ( 3 ) } ( m - 3 ) = 3$ . Pero $f ^ { f ( m - 3 ) } ( 3 ) = 3 = f ^ 0 ( 3 )$ lleva a $f ( m - 3 ) = 0$ lo cual es imposible. Por lo tanto, el único caso posible es $m = 2$ , según se desee.

Por último, utilizamos la inducción fuerte sobre $n$ para demostrar que $f ( n ) = n + 1$ para cada número entero positivo $n \ge 3$ . Tenga en cuenta que como $n \ge 3$ si dejamos que $a = \left\lfloor \frac { n + 1 } 2 \right\rfloor$ y $b = \left\lceil \frac { n + 1 } 2 \right\rceil$ entonces $a$ y $b$ son enteros positivos menores que $n$ tal que $a + b = n + 1$ . Por hipótesis de inducción, supongamos que $f ( m ) = m + 1$ para cada número entero positivo $m$ menos de $n$ . Esto demuestra que $f ^ { n - m } ( m ) = n$ para cada número entero positivo $m$ menos de $n$ . Por lo tanto, utilizando \eqref {0} tenemos $$f ( n + 1 ) ^ 2 = f ( a + b ) ^ 2 = f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ^ { a + 1 } ( b ) f ^ { b + 1 } ( a ) \\ = f ^ { n + 2 - b } ( b ) f ^ { n + 2 - a } ( a ) = f ^ 2 \left( f ^ { n - b } ( b ) \right) f ^ 2 \left( f ^ { n - a } ( a ) \right) = \left( f ^ 2 ( n ) \right) ^ 2 \text .$$ Por lo tanto, tenemos $f ( n + 1 ) = f \big( f ( n ) \big)$ y, por tanto, por la inyectividad de $f$ , $f ( n ) = n + 1$ , según se desee.