Exercícios Resolvidos Matematica Discreta - Combinatoria e Contagem

Matemática Discreta Exercícios de Combinatória de Contagem As referências citadas nesta lista de exercícios correspondem à terceira edição do livro de Scheinerman e à oitava edição do livro de Rosen P1 Scheinerman Exercício 89 De quantas formas uma torre preta e uma torre branca podem ser posicionadas em casas distintas de um tabuleiro de xadrez 8 8 de maneira que nenhuma delas esteja ameaçando a outra Em outras palavras elas não podem estar em uma mesma fileira nem em uma mesma coluna do tabuleiro P2 Scheinerman Autoteste do Capítulo 2 Exercícios 2 e 3 a Determine o número de listas a b c compostas por três números inteiros em que 0 a b c 9 e a b c é par b Determine o número de listas a b c compostas por três números inteiros em que 0 a b c 9 e abc é par P3 Scheinerman Exercício 168 Seis homens e seis mulheres dãose as mãos para formar uma ciranda De quantas maneiras essa roda de ciranda pode ser formada supondo que homens e mulheres devam alternarse P4 Scheinerman Exercício 169 De quantas maneiras é possível fazer um colar ou uma pulseira com 20 contas distintas Dica Com três contas distintas é possível fazer um único colar P5 Scheinerman Exercício 1612 a Um clube de tênis tem 40 membros Uma tarde eles se reúnem para jogar partidas individuais um contra um Cada membro do clube joga contra outro membro de forma que vinte partidas são disputadas De quantas maneiras esse torneio pode ser organizado Observação Considere que as partidas possam ser disputadas simultaneamente em quadras idênticas Em outras palavras só interessa quem joga contra quem não se faz distinção quanto à ordem ou ao local das partidas Além disso a partida João vs Maria é idêntica a Maria vs João b Na tarde seguinte os membros do clube decidem jogar partidas de duplas equi pes de dois contra dois Os jogadores formam 20 duplas e cada dupla joga uma partida contra outra dupla com um total de dez partidas De quantas maneiras isso pode ser feito Observação Valem as considerações do item anterior A partida João e Maria vs Hansel e Gretel é idêntica a Hansel e Gretel vs Maria e João 1 P10 Scheinerman Exercício 175 Vinte pessoas se reúnem em uma festa Se cada uma aperta a mão de todas as outras exatamente uma vez quantos apertos de mão ocorrem P11 Scheinerman Exercício 176 Uma sequência binária é uma sequência uma lista composta pelos algarismos 0 e 1 por exemplo 0010110 Já uma sequência ternária é uma sequência composta pelos algarismos 0 1 e 2 por exemplo 0211210 a Quantas sequências binárias de n algarismos contêm exatamente k uns b Quantas sequências ternárias de n algarismos contêm exatamente k uns P12 Scheinerman Exercício 178 Cinquenta atletas disputam uma corrida de 10 quilômetros Quantos resultados di ferentes são possíveis A resposta depende do que estamos julgando Obtenha a resposta em cada um dos contextos abaixo supondo que empates não ocorram a Queremos saber em que lugar cada um dos 50 atletas termina a prova b A corrida é uma prova de qualificação e desejamos saber apenas quais são os dez primeiros colocados c A corrida é a final de um evento olímpico e só interessa quem ganha as medalhas de ouro prata e bronze P13 Scheinerman Exercício 1711 De quantas maneiras distintas podese particionar em dois blocos um conjunto com n elementos considerando que um dos blocos deva ter exatamente quatro elementos e o outro bloco portanto deve ter todos os elementos restantes Observação Esse problema tem uma pegadinha Tenha cuidado P14 Scheinerman Exercício 1718 Quantos retângulos podemos formar com as casas de um tabuleiro de xadrez m n Em um tabuleiro 2 2 por exemplo são 9 retângulos P15 Baseado em Rosen Exercícios 6515 e 6520 a Determine quantas soluções tem a equação x1 x2 x3 x4 x5 21 onde cada xj é um inteiro não negativo com x1 2 e x3 5 b Determine quantas soluções tem a inequação x1 x2 x3 11 onde cada xj é um inteiro não negativo Dica Introduza uma variável auxiliar x4 0 tal que x1 x2 x3 x4 11 Dizse que x4 é uma variável de folga pois ela corresponde à folga entre 11 e x1 x2 x3 3 P16 Scheinerman Exercício 191 Há quatro grandes grupos de pessoas cada um com mil membros Quaisquer dois destes grupos têm cem membros em comum Quaisquer três dos grupos têm dez membros em comum E há exatamente uma pessoa em todos os quatro grupos Conjuntamente quantas pessoas há nos quatro grupos P17 Scheinerman Exercício 193 Dos números inteiros entre 1 e 1000000 inclusive quantos não são divisíveis por 2 nem 3 nem 5 Dica Primeiro determine quantos são divisíveis por 2 3 ou 5 P18 Scheinerman Exercício 195 Quantas palavras de cinco letras podemos formar sem que duas letras consecutivas sejam iguais Uma palavra pode ser qualquer lista de 26 letras assim wenjw é uma palavra que devemos contar mas terra não é Aqui está uma solução simples Pelos métodos de contagem de listas que estudamos incluindo o Princípio Multiplicativo a resposta é 26 25 25 25 25 26 254 Apresente uma solução complicada usando o Princípio de InclusãoExclusão Em seguida mostre que as duas soluções coincidem P19 Scheinerman Exercício 197 Quantos números de seis algarismos não têm três algarismos consecutivos iguais Neste problema podemos considerar números cujos primeiros algarismos sejam 0 Assim devemos contar 012345 e 001122 mas não 000123 nem 122234 P20 Scheinerman Exercício 198 Considere o reticulado da figura abaixo Determine quantos caminhos distintos ligam o canto inferior esquerdo ao canto superior direito sem passar pelos pontos A e B Tais caminhos devem consistir de exatamente 18 passos sobre o reticulado nove para a direita e nove para cima Um caminho assim é exemplificado na figura P21 Scheinerman Autoteste do Capítulo 3 Exercício 10 Dez casais sentamse ao redor de uma grande mesa circular De quantas maneiras diferentes eles podem sentarse supondo que maridos e esposas devam sentarse lado alado Observe que se todos se deslocarem conjuntamente para a esquerda ou para a direita a disposição resultante não é considerada diferente 4 P22 Scheinerman Autoteste do Capítulo 3 Exercício 13 Há 21 alunosas em uma aula de química Osas alunosas devem formar pares para realizar tarefas no laboratório mas evidentemente alguém terá que trabalhar sozinhoa De quantas maneiras os pares podem ser formados P23 Scheinerman Autoteste do Capítulo 3 Exercício 17 Em uma escola com 200 crianças 15 delas são selecionadas para integrar o time de matemática e destas 2 são escolhidas como cocapitães De quantas maneiras isso pode ser feito P24 Scheinerman Autoteste do Capítulo 3 Exercício 20 Uma pizzaria oferece dez sabores distintos Ao pedir uma pizza grande você pode escolher o sabor de cada quarto da pizza assim pode escolher até quatro sabores diferentes a Quantas pizzas grandes distintas podem ser feitas com 4 sabores diferentes b Quantas pizzas grandes distintas podem ser feitas admitindo que os sabores possam ser repetidos Por exemplo calabresa portuguesa e dois quartos de sabor marguerita ou ainda três quartos de presunto e um de quatro queijos P25 Scheinerman Autoteste do Capítulo 3 Exercício 21 Seja n um número inteiro positivo Quantos multiconjuntos distintos podem ser obtidos tendo como elementos os inteiros de 1 a n onde cada um pode ser utilizado por no máximo três vezes Por exemplo se n 4 então 2 2 2 3 4 4 1 1 1 e o multiconjunto vazio são admissíveis Por outro lado os seguintes multiconjuntos não são admissíveis 1 1 2 2 2 2 tem 2s em excesso e 1 2 5 pois 5 n 5