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
=