md_aula7_2014_1

Prévia do material em texto

3 – Aplicações 
 
 
Exemplo 3.1 
 
 Consideremos a equação 
 
11xxxx 4321 =+++ . 
 
Soluções inteiras e positivas para esta equação são quádruplas ordenadas 
)x,x,x,(x 4321 de inteiros positivos tendo soma 11. Algumas soluções são: 
 
 
)2,2,4,3( , )1,1,8,1( , )3,4,2,2( . 
 
 
O número 11 pode ser escrito como 
 
 
1111111111111 =++++++++++ . 
 
 
Desejamos separar 11 em 4 parcelas, sendo cada uma delas um inteiro positivo. 
Isto pode ser feito introduzindo 3 barras dentre os 10 sinais de adição. Assim, 
temos que: 
 
 
 )3,4,2,2( � 11111|1111|11|11 =++++++++++ 
 
 )1,1,8,1( � 111|1|11111111|1 =++++++++++ 
 
)2,2,4,3( � 1111|11|1111|111 =++++++++++ 
 
 
 O número total de soluções inteiras e positivas da equação dada é igual ao 
número de maneiras de escolhermos 3 dentre os dez sinais + (para neles 
colocarmos as barras). O número então de soluções procuradas é 
 
120
!7!3
!10C10,3 == . 
 
 
 
 
Teorema 3.1 
 
 O número de soluções em inteiros positivos da equação 
 
1 2 rx x ... x m+ + + = , para 0m > , 
 
é dado por 1r 1mC
−
−
. 
 
Demonstração 
 
 Estamos interessados em expressar o inteiro positivo m como soma de r 
inteiros positivos. Para isso, devemos colocar 1r − barras entre os m 1’s. Assim, 
o valor de 1x será o número de 1’s que antecedem a primeira barra, o valor de 
2x , o número de 1’s entre a primeira e a segunda barra, e assim por diante, até 
rx que corresponde ao número de 1’s à direita da barra 1r − . 
 A cada possível distribuição das barras, temos uma única solução para a 
equação dada. Assim, devemos contar de quantas formas isto pode ser feito. 
Selecionamos 1r − dos 1m − possíveis locais para a colocação das barras. Isto 
pode ser feito de 1r 1mC
−
−
 maneiras diferentes. 
 
 
Exemplo 3.2 
 
 Encontrar o número de soluções em inteiros positivos das seguintes 
equações: 
 
(a) 5xx 21 =+ 
(b) 9xxxxx 54321 =++++ 
 
 
Solução 
 
(a) 4CCC 1412 151r 1m === −−−− 
 
(b) 70CCC 4815 191r 1m === −−−− 
 
 
 
 
 
 
 
Observação 
 
 Se considerarmos soluções inteiras não negativas, no caso da equação 
 
5xx 21 =+ 
 
teríamos duas novas soluções: 5x,0x 21 == e 0 x,5x 21 == . Teremos então 6 
soluções. 
 
 
 
 Vamos então obter uma fórmula para o número de soluções inteiras não-
negativas. Consideremos o caso geral em que temos n variáveis. Nesse caso, 
temos: 
 
 mx...xx n21 =+++ , (3.1) 
 
para 0x i ≥ . Somando 1 a cada ix , obtemos 
 
 nm)1x(...)1x()1(x n21 +=++++++ . (3.2) 
 
Se fizermos 
 
1xy i i += , 
 
para n1,2,...,i = , teremos 
 
nmy...yy n21 +=+++ , 
 
para 1y i ≥ . 
 
 Como o número de soluções em inteiros não-negativos de (3.1) é igual ao 
número de soluções em inteiros positivos de (3.2), temos que este número é dado 
por 
 
 
m
1nm
1n
1nm CC −+
−
−+ = . 
 
 
 
Assim, no exemplo 3.1 teríamos que o número de soluções em inteiros não-
negativos de 
 
11xxxx 4321 =+++ 
 
é igual ao número de soluções em inteiros positivos de 
 
15yyyy 4321 =+++ , 
 
que é igual a 364C314 = . No exemplo 3.2 (b), teremos um total de 715C913 = 
soluções inteiras não-negativas. 
 
 
Exemplo 3.3 
 
 Encontrar o número de soluções em inteiros não negativos da equação 
 
12xxxxx 54321 =++++ . 
Solução 
 
 O número de soluções em inteiros não negativos é 
 
1820CC 416
15
1512 ==
−
−+ . 
 
 
Observação 
 
 Esta equação possui 330CC 411
15
112 ==
−
−
 soluções em inteiros positivos. 
 
 
Exemplo 3.4 
 
 Encontrar o número de soluções em inteiros positivos maiores que 3 da 
equação 
 
17xxx 321 =++ . 
 
Solução 
 
 Procuramos soluções da forma )8,5,4( ou )4,4,9( . Subtraindo 3 unidades 
de cada terna ordenada, isto é, fazendo 
 
3xy i i −= , 
 
obtemos 
 
8yyy 321 =++ , 
 
para 1y
 i ≥ que corresponde a ternas do tipo )5,2,1( ou )1,1,6( . O número de 
soluções em inteiros positivos da ultima equação é 3 1 28 1 7C C 21
−
−
= = . 
 
 
Exemplo 3.5 
 
 Encontrar o número de soluções em inteiros positivos da equação 
 
20xxx 321 =++ , 
 
onde 5x 2 > . 
 
Solução 
 
 Nesse caso, devemos subtrair 5 unidades de 2x e assim obteremos uma 
solução em inteiros positivos para 
 
15yyy 321 =++ , 
 
onde 11 xy = , 5xy 22 −= e 33 xy = . O número de soluções inteiras positivas da 
solução em y é 91CC 21413 115 ==−− . 
 
 
Observação 
 
 Note que a mudança de variáveis que utilizamos estabelece uma relação 
biunívoca entre os conjuntos de soluções das duas equações. 
 
 
Exemplo 3.6 
 
 Encontrar o número de soluções em inteiros positivos para a inequação 
 
6xxxx0 4321 ≤+++< . 
 
Solução 
 
 Devemos contar o número de soluções em inteiros positivos para as 
seguintes equações: 
 
1xxxx 4321 =+++ , 
 
2xxxx 4321 =+++ , 
 
3xxxx 4321 =+++ , 
 
4xxxx 4321 =+++ , 
 
5xxxx 4321 =+++ , 
 
6xxxx 4321 =+++ . 
 
 
O número de soluções em inteiros positivos para cada uma das três primeiras 
equações é zero. Para as últimas três, temos 
 
151041CCCCCC 35343314 1614 1514 14 =++=++=++ −−−−−− . 
 
 
Exemplo 3.7 
 
 Encontrar o número de soluções em inteiros não-negativos de 
 
18xxxxx 54321 =++++ , 
 
nas quais exatamente 2 incógnitas são nulas. 
 
Solução 
 
 Devemos contar o número de soluções em inteiros positivos de 
 
18yyy 321 =++ , 
 
e multiplicar pelo número de escolhas das duas incógnitas que terão valor nulo. 
Assim, temos 
 
136010136CC 25
13
118 =⋅=⋅
−
−
 .