DemonstraçõesDemonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Fórum de coletânea das melhores demonstrações de teoremas de matemática.
Se você quiser postar uma demonstração aqui, poste, inicialmente, no fórum correspondente utilizando o título "Demonstração Teorema X" e substitua com o nome do teorema/fórmula que você postou e, depois, envie o link para um moderador pedindo para sua mensagem ser movida para o fórum "Demonstrações". Somente moderadores poderão mover sua mensagem para este fórum.

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
MateusQqMD
6 - Doutor
Mensagens: 2410
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 29-07-20
Localização: Fortaleza
Mai 2019 04 16:49

Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Mensagem não lida por MateusQqMD »

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]

[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]

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!


Última edição: MateusQqMD (Ter 02 Jun, 2020 01:03). Total de 4 vezes.
Razão: adicionar vídeo.



Movido de Ensino Médio para Demonstrações em Ter 07 Mai, 2019 17:15 por csmarcelo

Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 4611
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 07-08-20
Jul 2019 19 18:23

Re: Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Mensagem não lida por csmarcelo »

De outra forma, [tex3]CR^k_m=C^{k+m-1}_m[/tex3]




Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 4611
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 07-08-20
Set 2019 02 09:42

Re: Demonstração - Número de Soluções Inteiras e Não Negativas de Uma Equação

Mensagem não lida por csmarcelo »

Aqui eu demonstrei o número de soluções inteiras e positivas de uma equação linear.




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Demonstrações”