[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Número de soluções de sistema linear - Correção



on 07.08.03 01:38, Alexandre Daibert at alexandredaibert2@ig.com.br wrote:

...
> O problema é determinar o número de soluções
> inteiras não negativas do sistema:
> 16a + 8b + 4c + 2d + e = 23
...

Oi, Alexandre:

A solucao classica pra esse tipo de problema eh via series formais (vide
artigo do Eduardo Tengan na Eureka 11).

No caso, nem precisamos usar series infinitas, mas apenas polinomios.
Precisamente, voce estah interessado no coeficiente de x^23 do polinomio
formal:

f(x) = a(x)*b(x)*c(x)*d(x)*e(x), onde:

a(x) = 1 + x^16
b(x) = 1 + x^8 + x^16 = (x^24-1)/(x^8-1)
c(x) = 1 + x^4 + x^8 + x^12 + x^16 + x^20 = (x^24-1)/(x^4-1)
d(x) = 1 + x^2 + x^4 + x^6 + ... + x^20 + x^22 = (x^24-1)/(x^2-1)
e(x) = 1 + x + x^2 + x^3 + ... + x^21 + x^22 + x^23 = (x^24-1)/(x-1)

Voce consegue ver o porque disso?

Logo:
f(x) = (1+x^16)*(x^24-1)^4/((x^8-1)*(x^4-1)*(x^2-1)*(x-1))

Pondo esta expressao para f(x) (que de fato eh um polinomio de grau 97) para
ser avaliada pelo PARI-GP, eu achei que o coeficiente de x^23 eh igual a 74.

Logo, existm 74 solucoes inteiras nao-negativas para a sua equacao.

Naturalmente, Mathematica, Matlab ou Maple tambem podem ser usados. O que eu
nao recomendo eh fazer na mao. Nao soh ha uma grande chance de voce errar
alguma conta, mas tambem voce vai ficar de saco tao cheio que corre o risco
de comecar a odiar matematica e abondonar esta bela ciencia pela razao
errada.

O PARI-GP eh um software de matematica (especialmente teoria dos numeros)
que pode ser baixado gratuitamente da internet.
O site eh este aqui:
http://www.parigp-home.de/

Um abraco,
Claudio.

=========================================================================
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
=========================================================================