2011/11/23 Fabio Silva <cacar...@yahoo.com> > > Meu aluno me pegou... > > "Quantas são as soluções inteiras não negativas para: 25x + 10y + 5z + w = 37" > > Saí no braço contando cada quadra de resultados e achei 24. > > Mas, como pensar sem ter que contar as soluções uma uma? Bom, a primeira coisa a fazer é olhar as divisibilidades. Daí, w = 2 mod 5 (porque o resto é divisível por 5) e daí você tem que resolver 5x + 2y + z = (37 - w)/5. Para cada valor de w, isso dá uma equação com 3 variáveis.
Bom, daí você vai "no braço", mas dá pra montar um esqueminha recursivo (que evita "contar tudo", mesmo se no fim das contas é o que você vai acabar fazendo) onde as variáveis "vão entrando" conforme o lado direito aumenta. (37 - w)/5 pode ser 7, 6, 5, 4, 3, 2, 1, 0. Se for 0, tem uma solução apenas(z = 0). Se for 1, idem (z = 1). Se for 2, tem duas soluções (2y + z = 2, tem y=1, z=0 ou z=2) Se for 3, idem (aumente z de um em cada uma). Se for 4, tem 3 soluções. Se for 5, "idem" + 1 solução x = 1 => 4 soluções Se for 6, tem 4 soluções com x=0, mais uma solução com x=1. Se for 7, "idem" para x=0, e dessa vez tem duas soluções com x=1 (repare que isso é igual à 2y + z = 2, e é assim que funciona a recorrência). 1+1+2+2+3+(3+1)+(4+1)+(4+2)=24 Uma outra idéia (que eu acho que dá mais trabalho, para números pequenos como o seu, mas que é mais geral) é montar uma recorrência polinomial dependendo da congruência do lado direito módulo o mmc dos fatores : http://math.stackexchange.com/questions/30638/count-the-number-of-positive-solutions-for-a-linear-diophantine-equation > Obrigado > > Fabio MS Abraços, -- Bernardo Freitas Paulo da Costa ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =========================================================================
