Lista-1

Prévia do material em texto

Lista 1 de Matema´tica Combinato´ria (marc¸o de 2012)
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 Quantos sa˜o os anagramas de PARAGUAI que comec¸am por vogal?
11 De quantos modos e´ poss´ıvel comprar 7 sorvetes em uma loja que os oferece em 4 sabores?
12 Quantas sa˜o as soluc¸o˜es inteiras e na˜o negativas de x + y + z = 5?
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 da equac¸a˜o x + y + z = 20, nas quais nenhuma inco´gnita e´
inferior a 2?
15 Quantos sa˜o os anagramas da palavra PIRACICABA que na˜o possuem duas letras A juntas?
16 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.
17 Quantos nu´meros ı´mpares, de algarismos distintos, existem entre 100 e 999?