Deje $f$ ser una función de los números enteros positivos en los enteros positivos y que satisface $f(n + 1) > f(n)$ $f(f(n)) = (f \circ f) (n) = 3n$ todos los $n$. Encontrar $f(100)$.
Esta es una de las preguntas que se presentan en una sesión del concurso de preparación de PUTNAM. Resulta que yo no puedo llegar desde el problema. Podría alguien darme una pista?
La función está claramente en aumento, por lo $f(99)<f(100)<f(102)$. Desde $f(99)=f(f(f(f(f(11)))))$, tiene sentido que nos gustaría saber $f(11)$. También, $f(102)=f(f(f(34)))$, por lo que queremos $f(34)$. Después de un tiempo, uno llega a la siguiente solución:
$f(1)\ne1$, ya que el $f(1)=1$ implica $3=f(f(1))=f(1)=1$. Por lo tanto, $1<f(1)$. Dado que la función es creciente, tenemos $f(1)<f(f(1))=3$. Por lo tanto, $1<f(1)<3$, e $f(1)=2$.
$f(2)=f(f(1))=3$, y $f(3)=f(f(2))=6$. $f(6)=f(f(3))=9$. Dado que la función es creciente, esto implica $f(4)=7$$f(5)=8$.
$f(7)=f(f(4))=12$. $f(9)=f(f(6))=18$, y $f(12)=f(f(7))=21$. De nuevo, debido a la creciente naturaleza de la $f$,$f(10)=19$$f(11)=20$.
$f(21)=f(f(12))=36$. $f(33)=f(f(20))=60$, y $f(36)=f(f(12))=63$. Por lo tanto, debido a $f$ está en aumento, $f(34)=61$ y $f(35)=62$. $f(60)=f(f(33))=99$, y $f(61)=f(f(34))=102$.
$f(99)=f(f(60))=180$ $f(102)=f(f(61))=183$ . Desde $f$ es creciente, $f(100)=181$$f(101)=182$.
Por lo tanto: $$f(100)=181$$
En general:
Si la base 3 de la representación de $n$ comienza con un $1$, $f(n)$ cambia a $2$;
Si la base 3 de la representación de $n$ comienza con un $2$, $f(n)$ cambia a $1$ y se multiplica por $3$.
Dado esto, simplemente debemos escribir $100 = 81 + 9 + 9 + 1 = 10201_3$, por lo que $$ f(100) = f(10201_3) = 20201_3 = \boxed{181}. $$
La prueba de esta descripción de la $\boldsymbol{f}$
Está claro que $f$, cuando se definen de esta manera, satisface $f(n+1) > f(n)$ $f(f(n)) = 3n$ todos los $n$. Así que si usted está asumiendo $f(100)$ está totalmente determinado por las presentes condiciones (dada la redacción del problema), usted puede parar aquí.
De lo contrario, tenemos que demostrar que el $f$ nos define es la única posible,$f$. Por lo tanto, fijar cualquier $g$ satisfacción $g(g(n)) = 3n$ $g(n+1) > g(n)$ todos los $n$; vamos a demostrar que $g(n) = f(n)$ todos los $n$ donde $f(n)$ es como la hemos definido.
Primero, tenga en cuenta lo siguiente: (1) $g$ es surjective en múltiplos de tres (ya que $g(g(n)) = 3n$); (2) $g(3n) = g(g(g(n))) = 3g(n)$; (3) $f$ es surjective en múltiplos de tres; (4) $f(3n) = 3f(n)$; y (5) $f(n+1) - f(n) \in \{1, 3\}$ todos los $n \ge 1$. (3) y (4) se justifica por el mismo razonamiento (1) y (2); (5) es la más importante y la que sigue a partir de nuestra definición de $f$, si no de los casos en la base de $3$ representación de $n$.
Vamos a proceder por la fuerte inducción. Para el caso base, como otros han observado, $1 < g(1) < 3$ implica $g(1) = 2$$g(2) = 3$, es decir,$g(1_3) = 2_3$$g(2_3) = 10_3$, lo $g$ está de acuerdo con $f$.
Para el paso inductivo, fix $k \ge 1$, supongamos que $g(i) = f(i)$$i \le k+1$, y considerar la posibilidad de $g(3k), g(3k+1), g(3k+2), g(3k+3)$. Tenemos $g(3k) = 3g(k) = 3f(k)$, e $g(3k+3) = 3f(k+1)$. Por (5), hay dos casos:
Si $f(k+1) - f(k) = 1$ $g$ a ser estrictamente creciente debemos recoger $g(3k+1) = 3f(k) + 1$, e $g(3k+2) = 3f(k) + 2$. En particular,$g(3k+1) = f(3k+1), g(3k+2) = f(3k+2)$.
Por otro lado, si $f(k+1) - f(k) = 3$ $g$ a ser surjective en múltiplos de $3$ debemos elegir $g(3k+1) = 3f(k) + 3$, $g(3k+2) = 3f(k) + 6$. En particular,$g(3k+1) = f(3k+1), g(3k+2) = f(3k+2)$.
Así que este completa la inducción.
Como por Akiva Weinberger comentario, tenemos que $f(1) = 2, f(3) = 6$$f(6)=9$. Como $f$ es creciente, esto obliga a $f(4)=7$$f(5)=8$.
Como $f(7)=f(f(4))=3\cdot4=12$,$f(12)=3\cdot7=21$. Del mismo modo, $f(9)=f(f(6))=18$. Por lo tanto tenemos: $$f(9)=18<f(10)<f(11)<f(12)=21$$ dando a $f(10)=19, f(11)=20$.
A continuación, $f(20)=f(f(11))=33$ $f(21)=f(f(12))=36$
Por lo $$f(33)=f(f(20))=60<f(34)<f(35)<f(36)=f(f(21))=63$$ Que las fuerzas de $f(34)=61$.
Por eso,$f(60)=f(f(33))=99$$f(61)=f(f(34))=102$.
Finalmente, $$f(99)=f(f(60))=180<f(100)<f(101)<f(102)=f(f(61))=183$$ y por lo $$f(100) = 181$$
La idea principal usada en esta solución es que si para algunos $k$, $f(k+1) = f(k)+1$, a continuación, $$f(3k)=f(f(f(k)))=3f(k)<f(3k+1)<f(3k+2)<f(3k+3)=f(f(f(k+1)))=3f(k+1) =3(f(k)+1) = 3f(k) +3$$ por lo $f(3k+1)=f(3k)+1$$f(3k+2)=f(3k)+2$. Como corolario, si podemos aplicar esto a $k$, también podemos aplicarlo a $k'=3k, 3k+1$ o $3k+2$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
