Re: [obm-l] 3 problemas

[kleinad@xxxxxxxxxx]

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   3   4   4
0   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
=========================================================================