md_aula4_2014_1

Prévia do material em texto

Exemplo 1.8 
 
Para todo inteiro n , a função u(n) é definida por 
 
1u(1) = 
5u(2) = 
)2u(n2)1u(nu(n) −+−= , 
 
para todo 2n > . Prove, usando o princípio da indução, que nn )1(2u(n) −+= . 
 
Demonstração 
 
Passo inicial: P(1) e P(2) são verdadeiras, pois 
 
)1(u1)1(2 11 ==−+ 
)2(u5)1(2 22 ==−+ 
 
Hipótese de indução: a relação 
 
nn )1(2u(n) −+= 
 
é válida para todo n , tal que kn2 ≤< . 
 
 Devemos provar que a relação vale para 1kn += . Temos que 
 
)1u(k2u(k)1)u(k −+=+ 
 
[ ]1k1kkk )1(22)1(2 −− −++−+= 
 
1kkk )1(2)1(22 −−⋅+−+⋅= 
 
21k1k )1()1(2 −−+= −+ 
 
1k1k )1(2 ++ −+= , 
 
o que comprova que 1)P(k + é válida. Dessa forma, pela segunda forma do 
princípio da indução matemática, a função u(n) é dada por nn )1(2u(n) −+= para 
qualquer inteiro 1n ≥ . 
 
 
 
 
 
Capítulo 2 – Princípios Aditivo e Multiplicativo 
 
Princípio Aditivo 
 
 Se A e B são dois conjuntos disjuntos ( φ=∩ BA ) com, 
respectivamente, p e q elementos, então BA ∪ possui qp + elementos. 
 
Princípio Multiplicativo 
 
 Se um evento A pode ocorrer de m maneiras diferentes e, se, para cada 
uma dessas m maneiras possíveis de A ocorrer, um outro evento B pode 
ocorrer de n maneiras diferentes, então o número de maneiras de ocorrer o 
evento A seguido de B é nm ⋅ . 
 
 
Exemplo 2.1 
 
 Suponha que tenha entrado em cartaz 3 filmes e 2 peças de teatro e que 
Carlos tenha dinheiro par assistir a apenas 1 evento. Quantos são os eventos que 
Carlos pode fazer no sábado? 
 
Solução 
 
 Carlos pode assistir ao filme 1 ou ao filme 2 ou ao filme 3 ou à peça 1 ou à 
peça 2. Portanto, são 5 programas diferentes. 
 
Podemos identificar os conjuntos 
 
}F,F,{Ffilme} um éx |{xA 321== 
 
e 
 
 
}P,{P teatro}de peça uma éx |{xB 21== , 
 
donde 
 
 teatro}de peça umaou filme um éx |{xBA =∪ . 
 
Portanto, 523n(B)n(A)B)n(A =+=+=∪ . 
 
 
 
 
 
Exemplo 2.2 
 
 Se no exemplo 2.1 Carlos puder assistir a um filme e a uma peça, quantos 
são os programas que ele pode fazer no sábado? 
 
Solução 
 
 Casos possíveis: 
filme 1 e peça 1 
filme 1 e peça 2 
filme 2 e peça 1 
filme 2 e peça 2 
filme 3 e peça 1 
filme 3 e peça 2 
 
Assim, Carlos poderá escolher dentre 6 programas diferentes, se optar por assistir 
a um filme e a uma peça. 
 
 Podemos tomar como evento A a escolha do filme (que são 3) e como 
evento B a escolha da peça de teatro (que são 2). Portanto, Carlos pode escolher 
um filme e uma peça de 623B)n(A =⋅=× maneiras. 
 
 
Extensão do Princípio Aditivo 
 
 Se n21 A,...,A,A são conjuntos disjuntos dois a dois, e se iA possui ia 
elementos, então a união U
n
1i
iA
−
 possui ∑
−
n
1i
ia elementos. 
 
 
Extensão do Princípio Multiplicativo 
 
 Se um evento iA pode ocorrer de im maneiras diferentes, para 
n1,2,3,...,i = , então esses n eventos podem ocorrer, em sucessão, de 
n321 m...mmm ⋅⋅⋅⋅ maneiras diferentes. 
 
 
2.1 – Aplicações dos Princípios Aditivo e Multiplicativo 
 
 
Exemplo 2.3 
 
 De quantas maneiras podemos dar dois prêmios a uma classe de 10 
rapazes, de modo que os prêmios não sejam dados a um mesmo rapaz? 
Solução 
 
 O primeiro prêmio pode ser dado a qualquer um dos 10 rapazes. O 
segundo prêmio poderá ser dado a qualquer um dos 9 rapazes restantes. 
Portanto, há 90910 =⋅ maneiras. 
 
 
Exemplo 2.4 
 
 De quantas maneiras podemos dar 2 prêmios a uma classe de 10 rapazes, 
se é permitido que ambos sejam dados a um mesmo rapaz? 
 
Solução 
 
 O primeiro prêmio pode ser dado a qualquer um dos 10 rapazes. O 
segundo prêmio também pode ser dado de 10 maneiras. Portanto, os 2 prêmios 
podem ser dados de 1001010 =⋅ maneiras. 
 
 
Exemplo 2.5 
 
 Em uma estante existem 5 livros diferentes de Matemática, 7 livros 
diferentes de Física e 10 livros diferentes de Química. De quantas maneiras 2 
livros podem ser escolhidos com a condição de que eles não sejam da mesma 
matéria? 
 
Solução 
 
 Possíveis escolhas: 
 
a) Matemática e Física � 3575n1 =⋅= 
b) Matemática e Química � 50105n 2 =⋅= 
c) Física e Química � 70107n3 =⋅= 
 
Logo, existem 155705035nnn n 321 =++=++= maneiras de se escolher 
dois livros. 
 
Exemplo 2.6 
 
 Quantos são os anagramas de 2 letras formados por uma vogal e uma 
consoante escolhidas dentre 18 consoantes e 5 vogais? 
 
 
 
 
Solução 
 
 Para escolha de cada consoante temos 18 possibilidades e, para cada uma 
delas, temos 5 possibilidades para a escolha da vogal. Assim, para a escolha de 1 
vogal e 1 consoante existem 90518 =⋅ possibilidades. Para formarmos 
anagramas, basta que consideremos, para cada uma das escolhas, a 
possibilidade de ser consoante-vogal ou vogal-consoante. Portanto, há 
180902 =⋅ anagramas. 
 
 
Exemplo 2.7 
 
 Considerando os algarismos 1, 2, 3, 4 e 5, quantos números de 3 
algarismos distintos podem ser formados? 
 
Solução 
 
 Podemos considerar que temos 3 posições para serem preenchidas. A 
primeira posição pode ser preenchida de 5 maneiras, a segunda de 4 maneiras e 
a terceira de 3 maneiras. Portanto, há 60345 =⋅⋅ números de 3 algarismos 
diferentes formados com os dígitos dados. 
 
 
Observação 
 
Anagrama é uma espécie de jogo de palavras, resultado do rearranjo das letras de 
uma palavra para produzir outras palavras, utilizando todas as letras originais 
apenas uma vez.