Re: [obm-l] 3 problemas

[kleinad@xxxxxxxxxx]

As duas �ltimas tabelas estavam com alguns erros de conta... Abaixo, espero
ter consertado todos (setas <==== indicam onde estava errado)

Bruno Bruno (brunobbruno@gmail.com) escreveu:
>
>Estou com dificuldades com esses daqui:
>
>1) Qual o algarismo das unidades do n�mero x = 1^1 + 2^2 + 3^3 +.... +
>n^n  ?

Seja x(n) = 1^1 + 2^2 + 3^3 + ... + n^n.

De maneira geral, se p e q s�o primos distintos, x == a (mod p) e x == b
(mod q), temos
   x = k*p + a
   x = m*q + b
logo
   q*x = k*p*q + a*q
   p*x = m*p*q + b*p
o que somando d�
(p + q)*x == a*q + b*p (mod p*q)

Mas p + q � invert�vel mod p*q, portanto x == (a*q + b*p)/(p + q) (mod p*q).

Seja x_2(n) a classe de congru�ncia de x(n) mod 2. Analogamente para x_5(n).

Se n = 2*k + a, a = 0 ou 1, uma simples indu��o mostra que x_2(n) == (k + a -
 1) (mod 2).

Para x_5(n), usando o teorema de Euler-Fermat (se u == v (mod 5) e u == w
(mod fi(5) = 4) ent�o u^u == v^u == v^w (mod 5)) vem

x_5(n) == (1^1 + 2^2 + 3^3 + 4^4)  + (1^2 + 2^3 + 3^4 + 4^1) + (1^3 + 2^4 +
3^1 +  4^2) + ... (mod 5)

A soma das parcelas em par�nteses s�o claramente c�clicas em mmc(4,5) = 20,
portanto se n = 20*m + b, ent�o x_5(n) = m*x_5(20) +  x_5(b).

Felizmente n�o � dif�cil construir uma tabela de valores x_5(b), b = 1,
2, ..., 19; os valores a serem somados s�o assim:

1^1   2^2   3^3   4^4   0
1^2   2^3   3^4   4^1   0
1^3   2^4   3^1   4^2   0
1^4   2^1   3^2   4^3   0

Ordenadamente em b, da esquerda pra direita e de cima para baixo, estes s�o
os valores de b^b mod (5). Isto pode ser melhorado:

1    -1    2    1    0
1    -2    1   -1    0   <====
1     1   -2    1    0
1     2   -1   -1    0

Portanto, para obter x_5(b) "basta" ir somando, mod 5, ordenadamente at� a b-
�sima casa. Em particular, x_5(20) = 4, portanto se n = 20*m + b, b = 1,
2, ..., 19, tem-se x_5(n) = 4*m + x_5(b). Os valores de x_5(b) s�o (b = 1,
2, ..., 20)

1   0   2   3   3   <====
4   2   3   2   2   <====
3   4   2   3   3
4   1   0   4   4

Temos 2 + 5 = 7, e o inverso de 7 mod 10 � 3. Pelas observa��es iniciais,

x == 3*(2*x_5(n) + 5*x_2(n)) == 6*x_5(n) + 15*x_2(n) == 6*x_5(n) + 5*x_2(n)
(mod 10).

O x_2(n) � facilmente calcul�vel, o x_5(n) d� um pouco mais de trabalho, e
admito que a solu��o � feia. Seria �timo se algu�m obtivesse uma f�rmula
fechada para x_5(n)..

[]s,
Daniel

=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================