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:
Re: [obm-l] Número de soluções de sistema linear - Correção 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 [EMAIL PROTECTED] 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 [EMAIL PROTECTED] 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
=========================================================================