Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação
Enviado: Sáb 04 Mai, 2019 16:49
Durante o desenvolvimento de alguns problemas que comumente aparecem no fórum é exigido que sejam contadas as soluções inteiras e não negativas de uma equação linear. Por isso, resolvi deixar uma redação que possa ajudar na interpretação desses enunciados.
Exemplo 1. Quantas são as soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]
Solução. Para contarmos as soluções dessa equação, escrevemos [tex3]9[/tex3] como a soma de nove [tex3]1'\text{s}:[/tex3]
E separamos o lado esquerdo da igualdade em [tex3]4[/tex3] partes. Isso pode ser feito acrescentando três barras entre os [tex3]1'\text{s}.[/tex3] Por exemplo:
Cada barra é utilizada para separar duas incógnitas, sendo que cada disposição de barras gera uma solução para a equação. A divisão feita acima corresponde à solução:
Isto é, [tex3]x_1 \, = \, 3, \,\,\,\, x_2 \, = \, 3, \,\,\,\, x_3 \, = \, 2 \,\,\, \text{e} \,\,\, x_4 \, = \, 1.[/tex3]
Outras soluções são as seguintes:
O valor de [tex3]x_1[/tex3] será o número de [tex3]1'\text{s}[/tex3] à esquerda da primeira barra; o de [tex3]x_2,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a primeira e a segunda barra; o de [tex3]x_3,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a segunda e a terceira barra e, por fim, o de [tex3]x_4,[/tex3] o número de [tex3]1'\text{s}[/tex3] à direita da última barra.
Daí, podemos concluir que o número de soluções inteiras e não negativas da equação mostrada é dado pelo número de modos de arrumarmos em fila [tex3]12[/tex3] elementos dos quais [tex3]3[/tex3] são barras iguais e [tex3]9[/tex3] são [tex3]1' \text{s}[/tex3] iguais. Isto é, podemos fazer isso de [tex3]P_{\,12}^{\,3,9} = \frac{12!}{3!9!} = 220[/tex3] modos.
Logo, há [tex3]220[/tex3] soluções inteiras e não negativas para [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]
Caso geral. Calcular o número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + \, ... \, + x_k = m,[/tex3] onde [tex3]k[/tex3] e [tex3]m[/tex3] são naturais dados.
Solução. A ideia, novamente, é expressar o inteiro [tex3]m[/tex3] em função da soma de [tex3]1'\text{s}[/tex3] e utilizar barras para separá-los:
Logo, como temos [tex3]\text{m} \,\, 1'\text{s}[/tex3] e [tex3]k -1[/tex3] barras para separar [tex3]k[/tex3] incógnitas, o número de soluções é [tex3]P_{ \, m + k -1}^{ \, m, \,\, k-1} = \frac{(m + k -1)!}{m!(k-1)!}.[/tex3]
Exemplo 2. De quantos modos podemos comprar [tex3]3[/tex3] carros de um mesmo modelo onde a cor de cada um deles pode ser amarela, branca, laranja ou verde?
Solução. A resposta desse problema é equivalente ao número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 3.[/tex3] Onde [tex3]x_1[/tex3] é a quantidade de carros comprados da cor amarela, [tex3]x_2[/tex3] a quantidade de carros comprados da cor branca, [tex3]x_3[/tex3] a quantidade de carros comprados da cor laranja e [tex3]x_4[/tex3] a quantidade de carros comprados da cor verde.
A resposta é [tex3]P_{3 + 4 -1}^{3, \,\, 4-1} = \frac{(3 + 4 -1)!}{3!(4-1)!} = \frac{6!}{3!3!} = 20[/tex3] modos.
Nota: o número de permutações de [tex3]n[/tex3] objetos dos quais [tex3]n_1[/tex3] são iguais a [tex3]\alpha, \,\,[/tex3] [tex3]n_2[/tex3] são iguais a [tex3]\beta, \, ... \,\, [/tex3] e [tex3]n_n[/tex3] são iguais a [tex3]\gamma [/tex3] [tex3](n_1 + n_2 + \, .... \, + n_n = n)[/tex3] é:
O professor caju resolveu de maneira bastante didática em forma de vídeo uma questão do ENEM 2017 (questão 143 da prova azul) que mexe com essa ideia. Recomendo bastante que vejam!
Exemplo 1. Quantas são as soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]
Solução. Para contarmos as soluções dessa equação, escrevemos [tex3]9[/tex3] como a soma de nove [tex3]1'\text{s}:[/tex3]
[tex3]1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 9.[/tex3]
E separamos o lado esquerdo da igualdade em [tex3]4[/tex3] partes. Isso pode ser feito acrescentando três barras entre os [tex3]1'\text{s}.[/tex3] Por exemplo:
[tex3]1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 = 9.[/tex3]
Cada barra é utilizada para separar duas incógnitas, sendo que cada disposição de barras gera uma solução para a equação. A divisão feita acima corresponde à solução:
[tex3]\begin{array}{ccccccccc}
x_1 &&& &&& x_2 &&& &&& x_3 &&& &&& x_4 &&& \\
3 &&& | &&& 3 &&& | &&& 2 &&& | &&& 1 \\
\end{array}[/tex3]
x_1 &&& &&& x_2 &&& &&& x_3 &&& &&& x_4 &&& \\
3 &&& | &&& 3 &&& | &&& 2 &&& | &&& 1 \\
\end{array}[/tex3]
Isto é, [tex3]x_1 \, = \, 3, \,\,\,\, x_2 \, = \, 3, \,\,\,\, x_3 \, = \, 2 \,\,\, \text{e} \,\,\, x_4 \, = \, 1.[/tex3]
Outras soluções são as seguintes:
[tex3]1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} 1 \, = \, 9 \,\,\,\,\,\,\,\,\,\,\,\,\, (2, \,\, 4, \,\, 2, \,\, 1)[/tex3]
[tex3]| \hspace{0,4cm} 1 + 1 + 1 + 1 \hspace{0,4cm} | \hspace{0,4cm} \hspace{0,4cm} | \hspace{0,4cm} 1 + 1 + 1 + 1 = \, 9 \,\,\,\,\,\,\,\,\,\,\,\,\, (0, \,\, 4, \,\, 0, \,\, 4)[/tex3]
O valor de [tex3]x_1[/tex3] será o número de [tex3]1'\text{s}[/tex3] à esquerda da primeira barra; o de [tex3]x_2,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a primeira e a segunda barra; o de [tex3]x_3,[/tex3] o número de [tex3]1'\text{s}[/tex3] entre a segunda e a terceira barra e, por fim, o de [tex3]x_4,[/tex3] o número de [tex3]1'\text{s}[/tex3] à direita da última barra.
Daí, podemos concluir que o número de soluções inteiras e não negativas da equação mostrada é dado pelo número de modos de arrumarmos em fila [tex3]12[/tex3] elementos dos quais [tex3]3[/tex3] são barras iguais e [tex3]9[/tex3] são [tex3]1' \text{s}[/tex3] iguais. Isto é, podemos fazer isso de [tex3]P_{\,12}^{\,3,9} = \frac{12!}{3!9!} = 220[/tex3] modos.
Logo, há [tex3]220[/tex3] soluções inteiras e não negativas para [tex3]x_1 + x_2 + x_3 + x_4 = 9.[/tex3]
Caso geral. Calcular o número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + \, ... \, + x_k = m,[/tex3] onde [tex3]k[/tex3] e [tex3]m[/tex3] são naturais dados.
Solução. A ideia, novamente, é expressar o inteiro [tex3]m[/tex3] em função da soma de [tex3]1'\text{s}[/tex3] e utilizar barras para separá-los:
[tex3]\underbrace{ 1 + 1 + 1 + \,\, ... \,\,+ 1 }_{ \text{m} \,\, 1'\text{s} } \,\,\, \underbrace{ | \,\, | \,\, | \,\, ... | \,\, | \,\, }_{ k -1 \,\, \text{barras} } [/tex3]
Logo, como temos [tex3]\text{m} \,\, 1'\text{s}[/tex3] e [tex3]k -1[/tex3] barras para separar [tex3]k[/tex3] incógnitas, o número de soluções é [tex3]P_{ \, m + k -1}^{ \, m, \,\, k-1} = \frac{(m + k -1)!}{m!(k-1)!}.[/tex3]
Exemplo 2. De quantos modos podemos comprar [tex3]3[/tex3] carros de um mesmo modelo onde a cor de cada um deles pode ser amarela, branca, laranja ou verde?
Solução. A resposta desse problema é equivalente ao número de soluções inteiras e não negativas da equação [tex3]x_1 + x_2 + x_3 + x_4 = 3.[/tex3] Onde [tex3]x_1[/tex3] é a quantidade de carros comprados da cor amarela, [tex3]x_2[/tex3] a quantidade de carros comprados da cor branca, [tex3]x_3[/tex3] a quantidade de carros comprados da cor laranja e [tex3]x_4[/tex3] a quantidade de carros comprados da cor verde.
A resposta é [tex3]P_{3 + 4 -1}^{3, \,\, 4-1} = \frac{(3 + 4 -1)!}{3!(4-1)!} = \frac{6!}{3!3!} = 20[/tex3] modos.
Nota: o número de permutações de [tex3]n[/tex3] objetos dos quais [tex3]n_1[/tex3] são iguais a [tex3]\alpha, \,\,[/tex3] [tex3]n_2[/tex3] são iguais a [tex3]\beta, \, ... \,\, [/tex3] e [tex3]n_n[/tex3] são iguais a [tex3]\gamma [/tex3] [tex3](n_1 + n_2 + \, .... \, + n_n = n)[/tex3] é:
[tex3]P_{\,n}^{ \,n_1, \, n_2, \, ... \,, \, n_n} = \frac{n!}{n_1!\,n_2! \, ... \, n_n!}[/tex3]
O professor caju resolveu de maneira bastante didática em forma de vídeo uma questão do ENEM 2017 (questão 143 da prova azul) que mexe com essa ideia. Recomendo bastante que vejam!