[obm-l] OBM 2004 - Nivel U - Prob. 4

["claudio.buffara" <claudio.buffara@xxxxxxxxxxxx>]

Aqui vai minha solução - construtiva - pra esse problema.

Obviamente, comentários serão bem-vindos.

 

Para 1 <= i <= k, seja R_i um vetor de Z^n tal que <R_i,P_i> = 0

(<X,Y> = X(1)*Y(1) + X(2)*Y(2) + ... + X(n)*Y(n) = produto interno usual de X e Y).

 

Seja S um vetor de Z^n tal que <S,Q> = 0.

 

Como, para 1 <= i <= k, (P_i - Q)/p não pertence a Z^n, vai existir, para cada i, um j(i) (1 <= j(i) <= n) tal que a j(i)-ésima coordenada de P_i - Q não é divisível por p.

 

Sendo assim, consideremos o polinômio f(X), dado por:

 

f(X) = <S,X>*Produto(1<=i<=k) <R_i,X> + Produto(1<=i<=k) (P_i(j(i)) - X(j(i)))

 

Para cada i <1 <= i <= k), f(P_i) = 0, pois <R_i,P_i> = 0, o que anula o primeiro produtório, e P_i(j(i)) - P_i(j(i)) = 0, o qua anula o segundo.

 

Por outro lado,

f(Q) =

<S,Q>*Produto(1<=i<=k) <R_i,Q> + Produto(1 <=i<=k) (P_i(j(i)) - Q(j(i)) =

0*Produto(1<=i<=k) <R_i,Q> + Produto de k inteiros não divisíveis por p =

Produto de k inteiros não divisíveis por p =

Inteiro não divisível por p.

 

Logo, f(P_i) = 0 para 1 <= i <= k  e  f(Q)/p não pertence a Z^n.

  

 

[]s,

Claudio.