Matemática Discreta - Lista 1

Prévia do material em texto

Lista 1 de Matemática Combinatória (Indução, Prinćıpios Aditivo e Multiplicativo, Aplicações)
1 Prove usando indução matemá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 números primos inteiros.
(vi) 2 divide n2 + n.
(vii) Seja {an} a sequência definida por: a1 = 1, a2 = 5, an = an−1 + 2an−2 para n ≥ 3.
Mostre que an = 2
n + (−1)n para todo n natural, n ≥ 1.
2 Quantos são os anagramas da palavra PRÁTICO que começam e terminam por vogal?
3 Quantos são os anagramas da palavra ÂNGULO que:
(i) começam por vogal
(ii) começam e terminam por vogal,
(iii) não tem juntas duas vogais nem duas consoantes,
(iv) nã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 número: N = 23 × 32 × 54 ? E o nú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 triângulos
existem com vértices em 3 desses 13 pontos?
7 De quantos modos 5 moç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 crianças, de modo que duas determinadas
dessas crianças não fiquem juntas?
10 Encontre o nú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 são os anagramas de PARAGUAI que começam por vogal?
12 Suponha que uma senha válida consista de 7 caracteres. O primeiro é uma letra escolhida do conjunto
{A,B,C,D,E, F,G} e cada um dos outros 6 caracteres é uma letra qualquer (em um alfabeto de 26 letras)
ou um digito qualquer (entre 10 digitos). Quantas senhas diferentes são posśıveis?
13 Quantas são as soluções inteiras e não negativas de x+ y + z = 5?
14 Quantas são as soluções inteiras e não negativas de x+ y + z ≤ 5?
15 Quantas são as soluções inteiras e não negativas da equação x+ y + z = 20, nas quais nenhuma incógnita é
inferior a 2?
16 Determine o nú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. Observação: estamos supondo que cada tipo de brinquedo tem um estoque suficiente para que o
problema tenha soluçã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 é relevante. Sabendo que todas as bandeiras devem ser
utilizadas, mas que nem todos os mastros precisam ser utilizados, encontre o número total de configurações.
18 Quantos são os anagramas da palavra PIRACICABA que nã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 até 999.
Como função de n, quantos tais números não tem dois d́ıgitos adjacentes iguais? Observe que, permitimos
747, mas não 344.
20 Quantos números ı́mpares, de algarismos distintos, existem entre 100 e 999?