[obm-l] problema 2 - obm-u

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

Acho que tive uma boa idéia pra resolver o problema 2 da obm-u segunda fase.

Primeiramente mude os 4 vetores e os polinômios de forma que estes passem a
ser (1, v[i]) com i =1..4.
grau(p) <= grau(q) = 2n e f1, f2, ..., f4 sejam polinômios em C[x] e
p + v[i]*q = f[i]²

então vemos que
(v[j]-v[i])q = f[j]² - f[i]² = (f[j] - f[i])(f[j] + f[i])

se tomarmos a decomposição de q em fatores lineares vemos que ela deve ter
2n fatores e que n deles devem ser fatores de f[j] - f[i] e os outros n
devem ser fatores de f[j] + f[i].

se tivermos um fator linear g que divida f[i] e f[j] então ele divide p e q,
o que não pode ocorrer pois p e q são primos entre si.

agora um fato interessante:
 - se um fator linear g é tq g|f2-f1 e g|f3-f1 então g|f3-f2
 - se g|f2+f1 e g|f3+f1, então g|f3-f2
 - se g|f2-f1 e g|f3+f1, então g|f3+f2

então ou temos que há exatamente n/2 termos em comum entre f2-f1 e f3-f1 e
exatamente n/2 termos em comum entre f2+f1 e f3+f1, ou não há termos em
comum entre esses dois pares (com certeza vão haver pares em que há termos
em comum dada a quantidade de diferenças possíveis)

acredito que manipulando os fatores lineares desses termos podemos chegar a
uma contradição, alguém resolveu o problema dessa forma?

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