Princípio de Inclusão e Exclusão

Prévia do material em texto

Lista 3 de Matema´tica Combinato´ria (Princ´ıpio de Inclusa˜o e Exclusa˜o)
1 Quantos inteiros entre 1 e 1000 sa˜o divis´ıveis por 3 ou por 7?
2 Quantos inteiros entre 1 e 1000 na˜o sa˜o divis´ıveis por 2, 3, 5 e 7?
3 Quantas arrumac¸o˜es dos d´ıgitos 0, 1, 2, . . . , 9 existem, nas quais o primeiro d´ıgito e´ maior que 1 e o u´ltimo
maior que 8 ?
4 Para um jantar numa mesa redonda sa˜o convidados 6 pares de inimigos, Deve-se acomoda´-los de modo a
separar os pares de inimigos. De quantos modos um mordomo pode acomoda´-los? E se tivermos n pares de
inimigos, n ≥ 2?
5 Quantas soluc¸o˜es inteiras existem para a equac¸a˜o x1 + x2 + x3 + x4 = 20 tais que 1 ≤ x1 ≤ 6, 1 ≤ x2 ≤ 7,
1 ≤ x3 ≤ 8 e 1 ≤ x4 ≤ 9
6 De quantas maneiras podemos permutar os inteiros 1, 2, . . . , 9 de modo que nenhum inteiro par ocupe seu
lugar natural?
7 Determine o nu´mero de sequeˆncias terna´rias de r d´ıgitos (r ≥ 2), onde cada um dos d´ıgitos 1 e 2 aparece ao
menos uma vez.
8 Quantos sa˜o os anagramas da palavra v´ırus que teˆm r em primeiro lugar, ou u em segundo lugar, ou v em
terceiro lugar, ou i em quarto lugar?
9 Numa festa 10 moc¸as deixam suas bolsas na chapelaria. De quantas maneiras suas bolsas podem ser retor-
nadas de maneira que nenhuma das moc¸as receba a sua bolsa original?
10 Sa˜o distribuidos n livros para n estudantes. Suponha que esses livros sa˜o devolvidos e distribuidos para
esses mesmos estudantes mais tarde. De quantas maneiras esses livros podem ser distribuidos de maneira
que nenhum estudante receba o mesmo livro duas vezes?