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.