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

[Alexandre Daibert <alexandredaibert2@xxxxxxxxx>]

Title:

Não, isto não caiu em vestibular nenhum, eu cheguei nisto no meio de um
problema, q eh o seguinte:
Tendo 10 caixas e 1000 moedas, colocar as caixas nas moedas de modo q
qualquer quantidade de 1 a 1000 moedas possam ser pegas de modo a não
abrir nenhuma caixa. Se não me engano este problema eh do homem q
calculava. tem uma solução mais usual para ele q eh ir colocando 1, 2,
4, 8, ... moedas em cada caixa, e no fim as q sobrarem colocar na
última caixa. Sobram 23 moedas, mas elas não precisam ser colocadas
necessariamente apenas na última caixa. Se vc pensar em cima do
problema vc chega q o número de soluções do problema é o número de
soluções inteiras não negativas da equação: 16a + 8b + 4c + 2d + e =
23. Claro q isto vai além do q se esperava q a pessoa fizesse no
problema. Cheguei a este resultado e quis, por curiosidade, saber como
calcular o número de soluções deste tipo de equação, visto q o cálculo
no braço seria muito trabalhoso. Pensei q houvesse alguma solução por
análise combinatória deste problema, porém mais avançada q a resolução
clássica da equação a + b + c + d = 10 por exemplo. Mas pelo que eu
entendi, este tipo de problema, pelo q vimos ateh aki, mesmo com
problemas menores, ou vc calcula todas as soluções no braço mesmo ou
joga em um computador. Não há método matemático q seja pouco
trabalhoso. Mas mesmo assim gostaria de agradecer imensamente ao
colega, pois as suas explicações contribuiram muito para mim.  :-) 

Se alguém quiser a minha resolução deste problema das caixas e como eu
cheguei a isso, depois me dê um toque q colocarei minha resolução aki
com paciência

Alexandre Daibert


Claudio Buffara escreveu:

A partir da expressao  fatorada eu acho que nao dah. Voce teria que multiplicar os 5 polinomios abaixo (a(x), b(x), etc...), o que relamente daria um trabalhao. Porisso eu usei o software.

Agora, esse problema caiu em algum vestibular? Se caiu, acho uma tremenda idiotice por parte da banca, pois uma vez achados os polinomios (o que eh facil, quando voce conhece o metodo) o problema vira 100% mecanico - apropriado para um computador.

Esta eh a beleza deste metodo de resolucao, o qual transforma um problema de combinatoria num problema mecanico de multiplicar polinomios.

Tente fazer este aqui no braco (muito menos trabalhoso):

"Achar o numero de solucoes inteiras nao negativas de de 3x + 2y + z = 10."

Depois compare a dificuldade do metodo dos polinomios formais com a da enumeracao pura e simples das solucoes (fazendo primeiro x = 0 e contando as solucoes de 2y + z = 10; depois x = 1 e contando as solucoes de 2y + z = 7; etc...)

Um abraco,
Claudio.

on 09.08.03 06:00, Alexandre Daibert at alexandredaibert2@ig.com.br wrote:

Tive uma dúvida nessa resolução. Depois de tudo feito, faltando calcular o coeficiente de x. supondo para um problema menor, como calcularíamos o coeficiente de x no grau 23 braço na expressão fatorada do tipo (1+x^16)*(x^24-1)^4/((x^8-1)*(x^4-1)*(x^2-1)*(x-1))

é q não podemos desmembrá-la, pois voltaríamos ao problema inicial.
obs: desculpe minha ignorância, mas sou um mero pobre, ignorante e humilde vestibulando...
:-P


Claudio Buffara escreveu:

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