Re: [obm-l] 3 Problemas de Teoria dos Números [EM INGLÊS]

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Daniel S. Braz wrote:

>Pessoal,
>
>Alguém poderia me dar uma dica na resolução desses aqui?
>
>1)Sets of 4 positive numbers are made out of each other according
>to the following rule: (a, b, c, d)  (ab, bc, cd, da).
>Prove that in this (infinite) sequence (a, b, c, d) will
>never appear again, except when a = b = c = d = 1. 
>  
>
suponha, sem perda de generalidade, que b > 1.
temos que ab > a e bc > b, agora observe que uma coordenada nunca pode 
diminuir, pois ela é sempre multiplicada por um termo >= 1, então (a, b, 
c, d) nunca mais pode aparecer na seqüência.

>2)Take a series of the numbers 1 and (-1) with a length
>of 2k (k is natural). The next set is made by multiplying 
>each number by the next one; the last is multiplied by the
>first. Prove that eventually the set will contain only ones.
>  
>
Tenho uma solução legal pra este...
Considere Z_2 = Z / (2Z), ou seja os inteiros módulo 2. Observe que {1, 
-1} com a operação de multiplicação é basicamente igual a {0, 1} com a 
operação de soma (tecnicamente falando, temos um isomorfismo levando 1 
-> 0 e -1 -> 1). Observe:
1*1 = 1  [0 + 0 = 0]
1*(-1) = -1 [0 + 1 = 1]
(-1)*(-1) = 0 [1 + 1 = 0]

Ok, agora a parte interessante. Seja m = 2^k e considere o anel
  R = Z_2[x] / <x^m + 1>

A aritmetica desse anel é bem favorável ao que pretendemos fazer, basta 
observar que dado um polinômio p em R
p(x) = a_0 + a_1 x + ... + a_{m-1} x^{m-1}, a multiplicação de p por x 
resulta em
x p(x) = a_0 x + ... + a_{m-2} x^{m-1} + a_{m-1} (x^m + 1) + a_{m-1}, 
mas como x^m + 1 = 0 neste anel, temos
x p(x) = a_{m-1} + a_0x + ... + a_{m-2} x^{m-1}

Então, (x + 1)p(x) = (a_0 + a_{m-1}) + (a_1 + a_2)x + ... + (a_{m-2} + 
a_{m-1})x^{m-1}

Note que esses coeficientes são definidos de forma isomorfa ao enunciado 
do problema! Então, nesse nosso anel, queremos mostrar que repetindo o 
processo, chegaremos no polinômio identicamente nulo! Isso quer dizer 
que (x+1)^r p(x) = 0 para algum r...

Como os coeficientes estão em Z_2, (x+1)^2 = x^2 + 2x + 1 = x^2 + 1, 
sendo assim,
(x+1)^4 = [(x+1)^2]^2 = [x^2 + 1]^2 = x^4 + 2x^2 + 1 = x^4 + 1 e, por 
indução, segue
(x+1)^{2^s} = x^{2^s} + 1 para todo s >= 0, em particular,

(x+1)^m p(x) = (x^m + 1) p(x) = 0 p(x) = 0.

[ ]'s
=========================================================================
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
=========================================================================