Indução, Princípio Aditivo e Princípio Multiplicativo

Prévia do material em texto

Lista 1 de Matema´tica Combinato´ria (Induc¸a˜o, Princ´ıpios Aditivo e Multiplicativo, Aplicac¸o˜es)
1 Prove usando induc¸a˜o matema´tica:
(i) 1 + 2 + 4 + . . .+ 2n−1 = 2n − 1.
(ii) 1× 1 + 2× 2 + 3× 4 + 4× 8 + . . .+ n× 2n−1 = (n− 1)2n + 1
(iii) 2 + 5 + 8 + . . .+ (3n− 1) = n(1 + 3n)/2
(iv) (1 + 1)(1 + 1/2)(1 + 1/3) . . . (1 + 1/n) = n+ 1
(v) Para cada inteiro positivo n, existem mais do que n nu´meros primos inteiros.
(vi) 2 divide n2 + n.
(vii) Seja {an} a sequeˆncia definida por: a1 = 1, a2 = 5, an+1 = an + 2an−1. Mostre que an = 2
n + (−1)n
2 Quantos sa˜o os anagramas da palavra PRA´TICO que comec¸am e terminam por vogal?
3 Quantos sa˜o os anagramas da palavra AˆNGULO que:
(i) comec¸am por vogal
(ii) comec¸am e terminam por vogal,
(iii) na˜o tem juntas duas vogais nem duas consoantes,
(iv) na˜o tem juntas as letras A e N.
4 De quantos modos podemos permutar as letras a,a,a,a,a,b,c,d,e de maneira que nao tenhamos duas letras a
adjacentes?
5 Quantos divisores tem o nu´mero: N = 23 × 32 × 54 ? E o nu´mero: M = am × bn×, cp, a,b e c primos ?
6 Marcam-se 5 pontos sobre uma reta R e 8 pontos sobre uma reta R1 paralela a R. Quantos triaˆngulos
existem com ve´rtices em 3 desses 13 pontos?
7 De quantos modos 5 moc¸as e 3 rapazes podem ser divididos em dois grupos de 4 pessoas de forma que cada
grupo inclua pelo menos um rapaz?
8 De quantos modos podemos dividir 18 pessoas em dois grupos de 9 pessoas cada?
9 De quantos modos podemos formar uma roda de ciranda com 9 crianc¸as, de modo que duas determinadas
dessas crianc¸as na˜o fiquem juntas?
10 Encontre o nu´mero de maneiras de se acomodarem 12 pessoas tal que 7 delas fiquem em uma mesa redonda
e as 5 restantes fiquem em um banco.
11 Quantos sa˜o os anagramas de PARAGUAI que comec¸am por vogal?
12 Suponha que uma senha va´lida consista de 7 caracteres. O primeiro e´ uma letra escolhida do conjunto
{A,B,C,D,E, F,G} e cada um dos outros 6 caracteres e´ uma letra qualquer (em um alfabeto de 26 letras)
ou um digito q ualquer (entre 10 digitos). Quantas senhas diferentes sa˜o poss´ıveis?
13 Quantas sa˜o as soluc¸o˜es inteiras e na˜o negativas de x+ y + z = 5?
14 Quantas sa˜o as soluc¸o˜es inteiras e na˜o negativas de x+ y + z ≤ 5?
15 Quantas sa˜o as soluc¸o˜es inteiras e na˜o negativas da equac¸a˜o x+ y + z = 20, nas quais nenhuma inco´gnita e´
inferior a 2?
16 Determine o nu´mero de maneiras de selecionar 15 brinquedos de 4 tipos diferentes: Tipo1, Tipo2, Tipo3 e
Tipo4, sendo que devem ser selecionados pelo menos 1 do Tipo1, pelo menos 2 do Tipo2 e pelo menos 3
do Tipo4. Observac¸a˜o: estamos supondo que cada tipo de brinquedo tem um estoque suficiente para que o
problema tenha soluc¸a˜o.
17 20 bandeiras distintas devem ser dispostas em 12 mastros distintos. Cada mastro comporta pelo menos 20
bandeiras, e a ordem das bandeiras em cada um deles e´ relevante. Sabendo que todas as bandeiras devem ser
utilizadas, mas que nem todos os mastros precisam ser utilizados, encontre o nu´mero total de configurac¸o˜es.
18 Quantos sa˜o os anagramas da palavra PIRACICABA que na˜o possuem duas letras A juntas?
19 Considere os inteiros decimais que possuem n d´ıgitos, n ≥ 2. Por exemplo, com n = 3 temos 100 ate´ 999.
Como func¸a˜o de n, quantos tais nu´meros na˜o tem dois d´ıgitos adjacentes iguais? Observe que, permitimos
747, mas na˜o 344.
20 Quantos nu´meros ı´mpares, de algarismos distintos, existem entre 100 e 999?