Sucesión periódica

Hay nuevos comentarios sin leer

Autor: ^DiAmOnD^ | Publicado el 2 de julio de 2012
Categorías: Juegos | Imprime este post

30 comentarios

Javier | 2 de julio de 2012 | 10:47

Vótalo 0
Este es muy sencillo.

Todos los cuadrados de numeros acabados en 9 y en 1 acaban en 1, en 4 los de 8 y 3, en 9 los de 7 y 3, en 6 los de 6 y 4, en 5 los de 5 y en cero los de 0.

Cuando hemos sumado 100 cuadrados, se suman 20 numero acabados en 1, que al sumarse acaban en 0, 20 acabados en 4, 20 en 9, 20 en 6, 10 en 5 y 10 en cero, que al sumarse todods ellos por separado, dan un numero suya suma acaba en 0, y obviamente la suma de todos es un numero acabado en 0.

Y esto hace que 1² acabe igual que 101², 2² acabe igual que 102², etc.
JJGJJG | 2 de julio de 2012 | 11:13

Vótalo 0
Javier, tu demostración es válida, pero observa que con los 20 primeros cuadrados también dan un número que acaba en 0, por lo que 1^2 acaba igual que 21^2, es decir, que el periodo es 20 y no 100.
pcrdeg | 2 de julio de 2012 | 11:52

Vótalo 0
No, me parece que la solución no es válida. Lo que Javier trata de demostrar es la periodicidad de
1^2+2^2`3^2+…+n^2
no la de
1^1+2^2+3^3+…+n^n que es lo que se pide.
Trackback | 2 jul, 2012

Bitacoras.com
pcrdeg | 2 de julio de 2012 | 13:17

Vótalo 0
Voy a demostrar qua la sucesión a(n) tiene período 100.

Para empezar, recuerdo un par de asuntos acerca de congruencias.

El primero es que si x=y (mod 10) entondes x^t=y^t (mod 10)

La segunda es que x^5=x (mod 10) Esto puede demostrarse a partir del teorema de Euler o, puesto que no hay muchos números que comprobar, puede hacerse directamente.

De la anterior expresión, obtenemos, probándolo por inducción, que x^(a+4b)=x^a (mod 10)

Ye estamos en condiciones de demostrar el problema.

Probamos primero que (x+20y)^(x+20y)=x^x (mod 10)
Tenemos que (x+20y)^(x+20y)=x^(x+20y)=x^x (mod 10) según las dos observaciones anteriores.

Ahora probaremos que a(100)=0.

Sea k tal que 0<k<=10.
Entonces (k+20t)^(k+20t)+(k+10+20t)^(k+10+20t)=k^k+k^(k+2) (mod 10)
Por tanto,
k^k+(k+10)^(k+10)+…+(k+80)^(k+80)+(k+90)^(k+90) =5•[ k^k+k^(k+2)] (mod 10)

Como k^k+k^(k+2) es siempre par, se tiene que k^k+(k+10)^(k+10)+…+(k+80)^(k+80)+(k+90)^(k+90)=0 (mod 10)

La suma “total” 1^1+2^2+3^3`+…+100^100 se puede ahora “trocear” en diez sumas de la forma k^k+(k+10)^(k+10)+…+(k+80)^(k+80)+(k+90)^(k+90), k=1, 2, …10, cada una múltiplo de 10 luego ” 1^1+2^2+3^3`+…+100^100 es múltiplo de 10 y de ahí que a(100)=0.

Ahora ya es sencillo, por inducción, probar que a(n+100)=a(n)

Si n=1 tenemos que 101^101 termina en 1, luego a(101)=1 pues a(100)=0.

Para que que nn+1 observamos que a(n+1) = a(n)+(n+1)^(n+1) (mod 10)
Como, por inducción, a(n+100)=a(n) y, (n+101)^(n+101)=(n+1)^(n+101)=(n+1)^(n+1) (mod 10) tenemos que
a(n+101)=a(n+100)+(n+101)^(n+101)=a(n)+(n+1)^(n+1)=a(n+1) (mod 10) luego a(n+101)=a(n+1)

[Nota.- Mediante una hoja de cálculo puede comprobarse que 100 en el menor período de la sucesión]
Pirer | 2 de julio de 2012 | 13:19

Vótalo 0
Dado que $\phi(10) = 4$ , se tiene que $(n+40)^{n+40} \equiv n^n (mod\; 10)$ . Sea $1^1 + 2^2 + \ldots + 40^{40} \equiv c (mod\; 10)$ .

Sea cual sea el valor de c, seguro que si lo sumamos 10 veces acaba en cero. Por tanto,
$a_{40} \equiv c\;\; (mod\; 10) \Rightarrow a_{40} + a_{40} + \ldots + a_{40} \equiv 0\;\; (mod\; 10)$ .

Por la primera igualdad, $a_{40} \equiv a_{80} - a_{40} \equiv a_{120} - a_{80} \equiv \ldots \;\; (mod\; 10)$ . Por tanto, sumando diez veces este valor obtenemos el cero: $a_{400} \equiv 0\;\; (mod\; 10)$ . De hecho, se tiene que $a_{400 + n} \equiv a_{n}\;\; (mod\; 10)\;\; \forall n$ ya que los coeficientes hasta 400 suman cero, y el resto coinciden: $(n+400)^{n+400}\equiv n^n\;\; (mod\; 10)$ .
SgV | 2 de julio de 2012 | 14:20

Vótalo 0
Coincido en que 40 es el periodo de la serie. Mi demostracion es definitivamente menos elegante.

El ultimo digito de cada potencia $n^n$ depende unicamente del valor de la unidad de $n$ , esto es de $n mod 10$. Por tanto tenemos que para los $n$ acabados en $1$ , la unidad de $n^n$ siempre valdra $1$ , para los que acaben en $2$ tomara ciclicamente uno de los valores dentro de $\{ 4, 8, 6, 2 \}$ . Para los acabados en $3$ uno dentro de $\{ 7, 1, 3, 9 \}$ , para los terminados en $4$ , $\{ 6, 4 \}$ , los acabados en $5$ , el valor $5$ , los acabados en $6$ , el valor $6$ , los acabados en $7$ , un valor dentro de $\{ 7, 9, 3, 1\}$ , los terminados en $9$ un valor dentro de $\{ 1, 9\}$ y los terminados en $0$ , el $0$ .

Evidentemente cuando todos los ciclos anteriores se vuelvan a realinear, finalizaremos un periodo (que no tiene por que ser el minimo). Esto sucede cuando se completa a los $40$ numeros (por construccion). Es facil (aunque tedioso) comprobar que no hay ningun subperiodo dentro de los $40$ primeros (la serie es: $1, 5, 2, 8, 3, 9, 6, 0, 1, 1, 2, 0, 1, 5, 0, 6, 5, 7, 6, 6, 7, 3, 6, 2, 7, 3, 6, 2, 3, 3, 4, 6, 5, 9, 4, 0, 1, 9, 8, 8$ ). Por tanto la sucesion es periodica y el minimo periodo es $40$.
pcrdeg | 2 de julio de 2012 | 14:29

Vótalo 0
Lo siento, pero es fácil comprobar conn una hoja de cálculo, como he indiocado, que el período es 100.

Por cierto, he encontrado una solución más general y elegantge, creo, basándome en este teoremilla de mi invención:
Teoremilla.
Si x(n) es una sucesión tal que x(n+p)=x(n) (mod q) entonces
s(n)=x(1)+x(2)+…+x(n)
cumple que s(n+pq)=s(n) (mod q)

Demostración.-
Probaré primero que s(pq)=0 (mod q)
S(pq)=s(1)+s(2)+….+s(pq)=
=[s(1)+s(2)+….+s(p-1)]+ [s(1+p)+s(2+p)+….+s(p-1+p)]+ [s(1+2p)+s(2+3p)+….+s(p-1+3p)]+…+ [s(1+(q-1)p)+s(2+(q-1)p)+….+s(p-1+(q-1)p)]
Cada expresión entre corchetes es idéntica módulo q, pues que x(n+p)=x(n) luego, por haber q corchetes, s(pq) es múltiplo de q.

Ahora probaré por inducción que que s(n+pq)=s(n) (mod q)
Si n=1, s(1+pq)=s(pq)+x(pq+1)=0+x(1)=x(1)=s(1) (mod q)
Para n+1, supuesto válido para n:
s(n+1+pq)=s(n+pq)+x(n+1+pq)=s(n)+x(n+1)=s(n+1) (mod pq)
q.e.d.

Respecto a nuestro problema, como la sucesión x(n)=n^n cumple
que x(n+10)=x(n) (mod 10) haciendo p=q=10 en el teoremilla se tiene que s(n) cumple que s(n+100)=s(n) (mod 10) o, equivalentemente a(n+100)=a(n)
Pau | 2 de julio de 2012 | 15:36

Vótalo 0
Pues yo creo que es 10

Demostración:

(n+10)^2 = n^2+20n+100

Los términos 20n+100 no afectan a las unidades para n>=1, por lo que las unidades de (n+10)^2 són las mismas que las de n^2

Así, el periodo és 10
Pau | 2 de julio de 2012 | 15:40

Vótalo 0
Perdón, en LaTex:

$(n+10)^2 = n^2+20n+100$

Los términos $20n+100$ no afectan a las unidades para $n>=1$ , por lo que las unidades de $(n+10)^2$ són las mismas que las de $n^2$
Pirer | 2 de julio de 2012 | 16:03

Vótalo 0
En respuesta a pcrdeg, creo que tu primera demostración es válida. Me gusta el truco de considerar que $k^k + k^{k+2}$ es par para encontrar que el período es como máximo de 100. En tu segundo post, creo que el teorema que pones es una generalización de mi solución. No obstante, tienes un error: 12^12 acaba en 6, mientras que 2^2 acaba en 4. Por tanto, es falso que $x(n+10) \equiv x(n)\; (mod\; 10)$ . Fijate en el teorema de Euler:
es.wikipedia.org/wiki/Teorema_de_euler

En respuesta a a SgV, tienes el mismo error: $12^{12} \equiv 6 \not\equiv 4 \equiv 2^2 \; (mod\; 10)$

En respuesta a Pau, fíjate que estamos elevando los números a ellos mismos, no al cuadrado. Habría, por tanto, que calcular $(n+10)^{n+10}$
pcrdeg | 2 de julio de 2012 | 16:33

Vótalo 0
Tienes razón, Piper. Una mala simplificación con la hoja de cálculo me ha hecho errar los cálculos.
En resumen: mi primera demostración es correcta y el período es 100.
El teoremilla es correcto.
Mi segunda demostración, usando el teoremilla, debe ectificarse usando p=20 con lo que se deduciría que a(n+200)=a(n) lo que, en efecto, demuestra la periodicidad pero no “acierta” con el período mínimo.

Y me gustaría pblicar la lista de los 200 primeros términos de la sucesión a(n) para que, salvo error en los cálculos, probar que el período, en efecto, es 100:
[1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 0, 1, 5, 2, 8, 3, 9, 2, 8, 7, 7, 8, 4, 7, 3, 8, 4, 1, 5, 4, 4, 5, 9, 6, 2, 7, 3, 6, 2, 1, 1, 2, 8, 1, 7, 2, 8, 5, 9, 8, 8, 9, 3, 0, 6, 1, 7, 0, 6, 5, 5, 6, 2, 5, 1, 6, 2, 9, 3, 2, 2, 3, 7, 4, 0, 5, 1, 4, 0, 9, 9, 0, 6, 9, 5, 0, 6, 3, 7, 6, 6, 7, 1, 8, 4, 9, 5, 8, 4, 3, 3, 4, 0, 3, 9, 4, 0, 7, 1, 0, 0]
Pau | 2 de julio de 2012 | 19:25

Vótalo 0
Cierto Pirer. ¡Qué error! Gracias.
golvano | 2 de julio de 2012 | 21:55

Vótalo 0
Siendo rigurosos (si no somos rigurosos aquí, ¿dónde vamos a serlo?), no se puede comprobar el período de una sucesión con una hoja de cálculo (salvo que calcules infinitos términos).
pcrdeg | 3 de julio de 2012 | 08:49

Vótalo 0
Ciertamente con una hoja de cálculo no se puede probar la periodicidad de la sucesión. Por eso lo he demostrado (dos veces).

En lo que sí ayuda una hoja de cálculo, cuando no se la pifia con las cuentas (la Excel soporta muy mal los números grandes y por eso he preferido usar Derive en un segundo intento) es en dar ideas para una hipòtesis. Por ejemplo, para intentar estimar el período.

Y, desde luego, para lo que muestra su utilidad es para desestimar hipótesis falsas: es evidente, por ejemplo, que 40 no es el período.
golvano | 3 de julio de 2012 | 09:45

Vótalo 0
Totalmente de acuerdo.

La segunda demostración se puede mejorar, tomando el mínimo común múltiplo de p y q, en lugar de pq. Así se obtendría el período mínimo.
pcrdeg | 3 de julio de 2012 | 10:12

Vótalo 0
No, me temo que no es tan sencillo.
El teoremilla afirma que si x(n) es una sucesión tal que x(n+p)=x(n) (mod q) entonces
s(n)=x(1)+x(2)+…+x(n)
cumple que s(n+pq)=s(n) (mod q)

Para q=10 y la sucesión x(n)=n^n se tiene que p=20.

Por tanto, el teoremilla afirma que 200=p•q es un período (módulo 10) de la sucesión.
Ya sabemos que el período mínimo es 100 así que el teoremilla no es eficiente en el sentido de encontrar el período mínimo pero sí lo es en el de demostrar la periodicidad.

Lo que, desde luego, no ocurre es que ese período mínimo sea el mcm(p,q) pues mcm(20,10)=20.
golvano | 3 de julio de 2012 | 10:52

Vótalo 0
Perdón, me he dado cuenta justo al escribirlo, pero no he podido enviar la rectificación hasta ahora.

Efectivamente, es un poco más complicado. El período mínimo sería:

$\frac{mcm(s(p),q)}{s(p)} * p$
Juanjo Escribano | 3 de julio de 2012 | 11:11

Vótalo 0
Pirer ¿que quieres decir con Phi(10) = 4? Luego no veo donde lo usas
Pirer | 3 de julio de 2012 | 13:11

Vótalo 0
Juanjo, según el teorema de Euler, $a^{\phi(n)} \equiv 1\; (mod\; n)$ si a y n son coprimos. En la primera fórmula que pongo, el desarrollo completo seria:

$(n+40)^{n+40} \equiv n^{n+40} \equiv n^{n+36} \equiv n^{n+32} \equiv \ldots \equiv n^n \; (mod \; 10)$

Esto es cierto para todos los numeros no divisibles ni por 2 ni por 5. En esos casos se tendria que comprobar aparte: si $n^n$ es divisible por 2, entonces también lo son n, n+40 y $(n+40)^{n+40}$ (que es el que necesitamos). Por tanto, basta comprobar que $(n+40)^{n+40} \equiv n^n \; (mod \; 5)$ .

Para el caso en que $n^n$ es divisible por 5 (o directamente por 10) se puede argumentar igual.
Juanjo Escribano | 4 de julio de 2012 | 11:35

Vótalo 0
Pirer
Lo que no conocía es la formúla del teorema de Euler.

El resto ya lo había entendido con mis propias cavilaciones, pero sin saber que había ese teorema.

Gracias
Emilce Alicia Morel Perez | 5 de julio de 2012 | 21:25

Vótalo 0
hola, que lindo blog! eres brillante quien quiera que seas..
Juanjo Escribano | 6 de julio de 2012 | 15:04

Vótalo 0
Creo poder demostrar que es periódica de periódo máximo igual a 100 sin fórmulas.

Los 10 primeros Nºs son 1 5 2 8 3 9 2 8 7 7 (mod(10))

Los diez siguientes se crean partiendo del 10º y se suma 1 en el primero, por lo que las series serán diferentes mientras losNº decenos sean diferentes, y no aparezca el 0.

Solo tenemos 10 Nºs diferentes (0 a 9), por lo que en el peor caso se habrá repetido 1 Nº antes o el 0 aparecerá en la posición 100. A partir de ahí la serie es periódica.

De haber periodicidad menor sería múltiplo de 10 cuando este sea cero o repita un Nº anterior, cosa que no ocurre en la tabla vista
Juanjo Escribano | 6 de julio de 2012 | 17:35

Vótalo 0
Y teniendo en cuenta que a(10) = 7 (mod(10)) y que por tanto
a(10) = 7 (mod(10)) … no repite hasta el 11 y que el 0 aparece en el Nº 100 (7*10=70 , =0 (mod(10)) y que eso ocurre en las 10 columnas que podemos crear (10*10) de columna y elemento a sumar se deduce que es periodica de periodo 100 y mínima
ajotatxe | 7 de julio de 2012 | 13:59

Vótalo 0
Consideramos la sucesión formada por las última cifras de $n^n$, cuando $n$ recorre los naturales. Esta sucesión es claramente periódica de periodo 10. Sus 10 primeros valores son 1, 4, 7, 6, 5, 6, 3, 6, 9, 0. Como $a_{n+100}$ es la última cifra del número obtenido sumando a $a_n$ diez veces la suma de estas cifras, es decir, un múltiplo de 10, $a_{n+100}=a_n$, como se quería demostrar.
ajotatxe | 7 de julio de 2012 | 14:04

Vótalo 0
Consideramos la sucesión formada por las última cifras de $n^n$ , cuando $n$ recorre los naturales. Esta sucesión es claramente periódica de periodo 10. Sus 10 primeros valores son 1, 4, 7, 6, 5, 6, 3, 6, 9, 0. Como $a_{n+100}$ es la última cifra del número obtenido sumando a $a_n$ diez veces la suma de estas cifras, es decir, un múltiplo de 10, resulta que $a_{n+100}=a_n$ , como se quería demostrar.

Perdón por la repetición; como se observa, el símbolo $ no sirve para escribir en LaTeX.
gaussianos | 7 de julio de 2012 | 21:25

Vótalo 0
ajotatxe, sí sirve, pero tienes que escribirlo como pone justo encima de la caja de texto de los comentarios (sin el espacio entre $ y latex):

$ latex código-latex$
Samuel Dalva | 8 de julio de 2012 | 21:45

Vótalo 0
CREO que una manera rápida de demostrar que es periódica con (al menos) período 100 podría ser:

a1 = 1^1 mod 10 = A1
a2 = 2^2 mod 10 = A2
a3 = 3^3 mod 10 = A3
.
.
.
a9 = 9^9 mod 10 = A9
.
.
.
a11 = (1+10)^(1+10) = A1^2
a12 = (2+10)^(2+10) = A2^2
.
.
.
a21 = (1+10+10)^(1+10+10) = A1^3
.
.
.
a91 = A1^10
.
.
.
a101 = A1^11 = (A1^10)*A1 = A1 <– período 100

Es decir, la serie 1^1, 2^2, 3^3, …., 101^101, 102^102, … es periódica.

Por tanto la serie 1^1+2^2+3^3+… es también periódica.
(esta afirmación es válida porque estamos en aritmética módulo 10)
Samuel Dalva | 8 de julio de 2012 | 21:57

Vótalo 0
Opps. Cagada.

a101 = A2^11 = (A1^10)*A1 = A1 <– período 100
a102 = A2
a103 = A3
etc..

Es falso.

Intento fallido 8(
Samuel Dalva | 8 de julio de 2012 | 22:13

Vótalo 0
También observo que se me han trastocado las fórmulas al “copiar y pegar”:

Lo que estaba haciendo era:

a1 = 1^1 = A1
a2 = 2^2 mod 10 = A2
a3 = 3^3 mod 10 = A3
.
.
.
a9 = 9^9 mod 10 = A9
.
.
.
a11 = (1+10)^(1+10) = A1*11^10
a12 = (2+10)^(2+10) = A2*12^10
.
.
.
etc.