[obm-l] Re: [obm-l] 2ª Vingança Olimpica-Prova

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

> 2)(Alex Abreu)Defina a sequencia
> x(1) natural e
> x(n+1)=1+(x(1)x(2)x(3)...x(n)).
> Prove que existe um primo p que nao divide ninguem da sequencia acima.[4]

para n > 1
x(n) = 1 + x(1).x(2)...x(n-1) => x(1).x(2)...x(n-1) = x(n) - 1
x(n + 1) = 1 + x(1)...x(n-1).x(n) = 1 + x(n)[x(n) - 1] = x(n)² - x(n) + 1

considere um primo q, e seja a = x(1)
x(1) = a (mod q)
x(2) = a + 1 (mod q)
x(n + 1) = x(n)² - x(n) + 1 (mod q) para n > 1

a partir desse momento considere os elementos de x como elementos de Zq
é evidente que x(n+1) = x(n) <=> x(n)² - 2x(n) + 1 = 0 <=> [x(n) - 1]² = 0
<=> x(n) = 1, mas se x(n) = 1, x(n-1) = 0 e queremos que q não divida nenhum
elemento da seqüência.

seja y = x(n)
x(n+2) = (y² - y + 1)² - (y² - y + 1) + 1 = y^4 - 2y³ + 2y² - y + 1
x(n+2) = x(n) <=> y = y^4 - 2y³ + 2y² - y + 1 <=>
y^4 - 2y³ + 2y² - 2y + 1 = 0

exemplo: se q = 5, 2 e 3 são raiz do polinômio acima e, tomando x(1) = 5m +
1, temos:
{x(n) em Zq, n natural} = { 1, 2, 3, 2, 3, 2, 3, ... } = { 1, 2, 3 }, para o
caso x(1) = 5m + 2, temos
{x(n) em Zq, n natural} = { 2, 3, 2, 3, ... } = { 2, 3 }, logo para os casos
x(1) = 5m + 1 ou 5m + 2, 5 não divide nenhum elemento da série

um simples programa de computador pode calcular as raízes do polinômio para
outros valores de q, sendo assim podemos provar que o enunciado é válido
para todos os x(1) das formas:
5m + 1, 5m + 2, 13m + 4, 13m + 7, 17m + 3, 17m + 12, 29m + 11, 29m + 16, 37m
+ 5, 37m + 30, 41m + 8, 41m + 31, 53m + 22, 53m + 29, 61m + 10, 61m + 49,
73m + 26, 73m + 45, 89m + 33, 89m + 54, 97m + 21, 97m + 74, 101m + 9, 101m +
90, 109m + 32, 109m + 75, 113m + 14, 113m + 97, 137m + 36, 137m + 99, 149m +
43, 149m + 104, ...

e a lista continuaria e continuaria... o que, apesar de não provar o
enunciado, indica que se existesse algum inteiro em que o enunciado falha
ele deveria ser bem peculiar!

[ ]'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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================