El que acaba tiene el resto del dia libre?

Question

Si f es una aplicacion del conjunto de enteros estrictamente positivos sobre si mismo, definida por:

f(1) =1, f(3)=3 y para todo n>= 1,

f(2n) = f(n)
f(4n+1)=2f(2n+1)-f(n)
f(4n+3)=3f(2n+1)-2f(n)

Determinar el numero de enteros n, 1<= n <=1988 para los cuales f(n)=n.

Answer 1

La respuesta es 92
____________________________
No desgraciadamente no son todos los impares (calculen f(11) para verificarlo)...

Es muy interesante tu pregunta y creo que sería bueno saber la solución. Soy totalmente sincero, a mi no se me ocurre como resolverlo de forma analítica. Sin embargo como tu conjunto de números es finito, siempre se puede echar mano de la computadora para resolverlo. Hacer un programita que lo resuelva no es difícil pero laborioso, sin embargo pues lo hice para ver si analizando su comportamiento me venia a la mente algún patrón.

Lo que preguntas la verdad es lo de menos, una vez escrito el programa verificar cuantos puntos fijos tiene se convierte en un problema de conteo el cual se puede usar la misma computadora entonces, si solo necesitas el dato la respuesta es 92. Hay 92 puntos fijos para enteros entre 1 y 1988. LO que yo preguntaría es.
¿Existe alguna condición para determinar si f(n) = n? Es claro que los pares no la cumplen pero ser impar no es condición suficiente, veamos los primeros 20 números que cumplen la condición…
1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 66, 73, 85, 93, 99 107,

Pues no, no le veo patrón…
________________________________
Me da pena decir donde construí el programa pero lo hice en Excel, simplemente en la primera columna puse n la segunda f(n) le di f(1) , f(3) f(2) a mano y puse la fórmula para f(4), f(5), f(6) y f(7) y después lo jale hasta la celda 1988. En la columna 3 le puse que me diera la diferencia entre n y f(n) para después contar los ceros con CONTAR.SI

Entonces lo interesante de la hoja de cálculo es
A B
[1] [1]
[2] [1]
[3] [3]
[4] [=INDICE(B$1: B$1988, ENTERO(A4/2), 1)]
[5] [=2*INDICE(B$1: B$1988, ENTERO(A5/2)+1, 1) –
INDICE(B$1: B$1988, ENTERO(A5/4), 1)]
[6] [=INDICE(B$1: B$1988, ENTERO(A6/2), 1)]
[7] [=3*INDICE(B$1: B$1988, ENTERO(A7/2),1) –
2*INDICE(B$1: B$1988, ENTERO(A7/4), 1)]

Espero que te sea útil y si alguien quiere resolver algebraicamente el problema, puede usar lo ya hecho.

Answer 2

Bueno, si se considera n=4k+1 y k=2^m entonces f(n)=n, claro que estos no son los unicos puntos fijos, pero es una respuesta analitica aunque parcial .
Para ver que el resultado es cierto, se puede probar por induccion que f(2k+1)=2k+1, y usando el hecho de que para k=2^m se tiene f(k)=1, entonces:

f(n) = f(4k+1) = 2f(2k+1)-f(k) = 2(2k+1)-1 = 4k+2-1 = 4k+1 = n

Para la parte de induccion: si k=2^0=1, f(2k+1)=f(3)=3
Suponemos se vale para k=2^m, es decir

f(2(2^m)+1) =2(2^m)+1, (hpt de induccion);

tenemos, para k=2^(m+1)
1) f(2k+1)= f(2( 2^ (m+1) ) +1) (sustitucion de k)
2) f(2k+1)= f(4(2^m) + 1) (de 1) paso aritmetico)
3)f(2k+1)= 2f(2(2^m) + 1) - f(2^m) (de 2) y la definicion de f)
4)f(2k+1)= 2(2(2^m) + 1)-1 (de 3) y por hpt de induccion)
5)f(2k+1)= 2(2^(m+1))+1 Lo que se queria demostrar

Por cierto, si k=2^m entonces n=4k+3 no es punto fijo salvo para m=0, es decir k=1

Espero alguien encuentre otros casos
Bye

Answer 3

pues todos los impares, es decir 994 enteros positovos.