Fundamentos de Teoria da Computação - Aula 06: Conjuntos e Contagem

Fundamentos de Teoria da Computação Aula 06 M A R C O S M A N S A N O F U R L A N AGENDA DA AULA Conjuntos e Contagem Conjuntos 41 Contagem 42 Princípio da inclusão e exclusão 43 Princípio das casas de pombos 43 CONJUNTOS A teoria dos conjuntos é uma das pedras fundamentais da matemática Muitos conceitos em matemática e em ciência da computação podem ser expressos de maneira conveniente na linguagem de conjuntos Operações podem ser efetuadas em conjuntos para gerar novos conjuntos Embora a maioria dos conjuntos de interesse para cientistas da computação seja finita ou enumerável existem conjuntos que têm tantos elementos que não podem ser enumerados CONJUNTOS Usaremos a ideia intuitiva de que um conjunto é uma coleção de objetos definição informal Em geral todos os objetos em um conjunto têm alguma propriedade em comum além de pertencerem ao mesmo conjunto qualquer objeto que tem essa propriedade pertence ao conjunto e qualquer objeto que não tem essa propriedade não pertence ao conjunto Isso é condizente com as utilizações da palavra conjunto nas aulas anteriores CONJUNTOS Notação Usaremos letras maiúsculas para denotar conjuntos e o símbolo para denotar pertenência em um conjunto Assim a A significa que a pertence a A ou é um elemento do conjunto A e b A significa que b não pertence ao conjunto A Usamos chaves para indicar um conjunto EXEMPLO 1 Se A violeta verde castanho então verde A e magenta A CONJUNTOS Os elementos em um conjunto não têm nenhuma ordem de modo que violeta verde castanho é o mesmo que verde castanho violeta Além disso cada elemento do conjunto é listado apenas uma vez é redundante listá lo de novo Dois conjuntos são iguais se contiverem os mesmos elementos Usando a notação da lógica de predicados temos A B significa xx A x B x B x A CONJUNTOS Ao descrever um conjunto particular temos que identificar seus elementos Para um conjunto finito podemos fazer isso simplesmente listando todos os elementos como fizemos com o conjunto A no Exemplo 1 Embora seja impossível listar todos os elementos de um conjunto infinito para alguns conjuntos infinitos podemos indicar a forma geral listando os primeiros elementos Assim poderíamos escrever 2 4 6 para expressar o conjunto S de todos os inteiros positivos pares S também pode ser definido por recorrência explicitandose um dos elementos de S e descrevendo depois os outros elementos de S em termos dos elementos já conhecidos CONJUNTOS Conjunto dos números inteiros positivos Enumeração 2 4 6 Recorrência 1 2 S 2 Se n S então n 2 S CONJUNTOS A maneira mais clara de se descrever esse conjunto S particular é por meio da propriedade que caracteriza os elementos do conjunto em palavras ou seja S x x é um inteiro positivo par que se lê o conjunto de todos os x tais que x é um inteiro positivo par CONJUNTOS Já temos agora três maneiras para tentar descrever um conjunto 1 Listar ou listar parcialmente seus elementos 2 Usar recorrência para descrever como gerar seus elementos 3 Descrever uma propriedade P que caracteriza seus elementos CONJUNTOS Para qualquer x dado Px ou é verdadeiro ou é falso De fato a notação para a lógica formal do Capítulo 1 vem novamente nos ajudar a tornar mais claro o que queremos dizer com uma propriedade que caracteriza os elementos de um conjunto S x Px significa xx S Px Px x S CONJUNTOS PROBLEMA PRÁTICO 1 Descreva cada um dos conjuntos a seguir listando seus elementos a x x é um inteiro e 3 x 7 b x x é um mês com exatamente 30 dias c x x é a capital do Brasil CONJUNTOS É conveniente usar uma notação padrão para determinados conjuntos de modo que possamos nos referir mais facilmente a eles Usaremos as seguintes notações N conjunto de todos os inteiros não negativos note que 0 N Z conjunto de todos os inteiros Q conjunto de todos os números racionais R conjunto de todos os números reais C conjunto de todos os números complexos CONJUNTOS Algumas vezes vamos nos referir ao conjunto que não tem elementos o conjunto vazio denotado por Ø ou por Por exemplo se S x x ℕ e x 0 então S Ø Note que Ø o conjunto que não tem elementos é diferente de Ø que é um conjunto com um único elemento em que esse elemento é o conjunto vazio EXEMPLO 2 Suponha que um conjunto A é dado por A x yy 0 1 2 e x y³ Como y não é uma variável livre aqui esse conjunto ainda é da forma A x Px Os elementos de A podem ser encontrados atribuindose a y cada um dos valores 0 1 e 2 e depois elevando ao cubo cada um desses valores Portanto A 0 1 8 Para B x x ℕ e yy ℕ e x y B x x ℕ e yy ℕ e x y escolhendo y 0 obtemos x 0 escolhendo y 1 obtemos x 0 ou 1 escolhendo y 2 obtemos x 0 1 ou 2 e assim por diante Em outras palavras B consiste em todos os inteiros não negativos menores ou iguais a algum inteiro não negativo o que significa que B ℕ Para o conjunto C x x ℕ e yy ℕ x y obtemos C 0 já que 0 é o único inteiro não negativo que é menor ou igual a todos os inteiros não negativos Ax xN e yy2345 xy xxA Use lógica formal para definir A B Quantas cartas devem ser retiradas de um baralho padrão com 52 cartas para se obter com certeza uma carta de um naipe preto A 1 7 9 15 B 7 9 C 7 9 15 20 Então as seguintes proposições entre outras são verdadeiras B C 15 C B A 7 9 B B A 7 A A C C A última proposição C é verdadeira porque a proposição xx x C é verdadeira já que x é sempre falsa Se 12 cartas forem retiradas de um baralho padrão pelo menos duas delas terão que ser do mesmo naipe RELAÇÕES ENTRE CONJUNTOS Suponha que B x Px e que A B Como todo elemento de A também pertence a B e P é uma propriedade que caracteriza os elementos de B todo elemento de A também tem a propriedade Px Os elementos de A herdam a propriedade P De fato para provar que A B mostramos que Px é válida para qualquer elemento arbitrário x A Se A for um subconjunto próprio de B então os elementos de A terão em geral alguma propriedade adicional não compartilhada por todos os elementos de B Essa é a mesma noção de herança que temos em uma linguagem de programação orientada a objeto para um tipo descendente ou subtipo ou tipo derivado O tipo descendente herda todas as propriedades e operações do tipo ascendente além de outras propriedades ou operações locais especializadas se necessário Quantas cartas devem ser retiradas de um baralho padrão com 52 cartas para se obter com certeza 2 damas B x x é um múltiplo de 4 e A x x é um múltiplo de 8 Temos então A B Para provar isso seja x A note que x é um elemento completamente arbitrário de A Precisamos mostrar que x satisfaz a propriedade que caracteriza os elementos de B isso significa que precisamos mostrar que x é um múltiplo de 4 Como x A x satisfaz a propriedade que caracteriza os elementos de A logo x é um múltiplo de 8 e podemos escrever x m 8 para algum inteiro m Essa equação pode ser escrita como x m 2 4 ou x k 4 em que k 2m de modo que k é um inteiro Isso mostra que x é um múltiplo de 4 portanto x B Existem números como 12 que são múltiplos de 4 mas não de 8 logo A B Outra maneira de descrever A é A x x k 4 e k é um número par Nessa forma é claro que os elementos de A herdaram a propriedade que caracteriza os elementos de B ser um múltiplo de 4 mas existe uma restrição adicional que faz com que A seja menos geral do que B Um serviço de encontros por computador tem uma lista contendo 50 homens e 50 mulheres São selecionados nomes aleatoriamente Quantos nomes têm que ser selecionados para garantir que apareçam nomes de uma pessoa de cada sexo PROBLEMA PRÁTICO 7 Sejam A x x ℝ e x² 4x 3 0 B x x ℕ e 1 x 4 Prove que A B Um serviço de empregados domésticos por computador tem uma lista contendo 50 homens e 50 mulheres São selecionados nomes aleatoriamente Quantos nomes têm que ser selecionados para garantir que apareçam dois nomes de pessoas do mesmo sexo Vamos provar que x x ℕ e x² 15 x x ℕ 2x 7 Sejam A x x ℕ x² 15 e B x x ℕ 2x 7 Para provar que A B vamos mostrar que A B e B A Para A B precisamos escolher um elemento arbitrário de A ou seja qualquer coisa que satisfaz a propriedade que caracteriza os elementos de A e mostrar que satisfaz a propriedade que caracteriza os elementos de B Seja x A Então x é um inteiro não negativo que satisfaz a desigualdade x² 15 Os inteiros não negativos cujos quadrados são menores do que 15 são 0 1 2 e 3 logo esses são os elementos de A O dobro de cada um desses inteiros não negativos é um número menor do que 7 Portanto todo elemento de A pertence a B e A B Vamos mostrar agora que B A Todo elemento de B é um inteiro não negativo cujo dobro é menor do que 7 Esses números são 0 1 2 e 3 e cada um deles tem o quadrado menor do que 15 logo B A Um grupo tem que conter quantas pessoas para se garantir que duas pessoas no grupo façam aniversário no mesmo dia Não esqueça os anos bissextos Para um conjunto S podemos formar um novo conjunto cujos elementos são os subconjuntos de S Esse novo conjunto é chamado o conjunto das partes de S e denotado por S EXEMPLO 6 Para S 0 1 S 1 0 1 Note que os elementos do conjunto das partes de um conjunto são conjuntos LEMBRETE Para encontrar S comece com Depois inclua todos os conjuntos com um único elemento pertencente a S depois com 2 elementos pertencentes a S com 3 elementos e assim por diante Em um grupo de 25 pessoas é verdade que existem pelo menos 3 pessoas que nasceram no mesmo mês PROBLEMA PRÁTICO 8 Para A 1 2 3 o que é A PROBLEMA PRÁTICO 9 Se S tem n elementos então S tem elementos Sua resposta também funciona para n 0 Prove que se quatro números forem escolhidos do conjunto 1 2 3 4 5 6 pelo menos um par tem que somar 7 Sugestão Encontre todos os pares de números do conjunto cuja soma seja 7 CONJUNTOS DE CONJUNTOS Para a base da indução tomamos n 0 O único conjunto sem elementos é Ø O único subconjunto de Ø é Ø logo Ø Ø um conjunto com 1 20 elementos Vamos supor que para qualquer conjunto com k elementos o conjunto de suas partes tem 2𝑘 elementos Seja S um conjunto com k 1 elementos e retire um desses elementos por exemplo x O conjunto que resta é um conjunto com k elementos logo pela hipótese de indução seu conjunto de partes tem 2𝑘 elementos Cada um desses elementos também pertence a S Os únicos elementos de S não incluídos são os que contêm x Todos os subconjuntos contendo x podem ser encontrados colocandose x em todos os subconjuntos que não o contém que são em número de 2𝑘 assim teremos 2𝑘 subconjuntos contendo x Juntos temos 2𝑘 subconjuntos não contendo x e 2𝑘 contendo x ou um total de 2𝑘 2𝑘 2 2𝑘 2𝑘1 subconjuntos Portanto S tem 2𝑘1 elementos Quantos números devem ser escolhidos do conjunto 2 4 6 8 10 12 14 16 18 20 para se garantir que pelo menos um par soma 22 Veja a sugestão do Exercício 25 OPERAÇÕES BINÁRIAS E UNÁRIAS Para ver exatamente o que é uma operação binária vamos considerar a subtração com mais detalhes Dados dois inteiros quaisquer x e y x y gera uma resposta e apenas uma e essa resposta sempre será um número inteiro Finalmente a subtração é efetuada em um par ordenado de números Por exemplo 7 5 não produz o mesmo resultado que 5 7 Um par ordenado é denotado por x y em que x é a primeira componente e y é a segunda A ordem é importante em um par ordenado assim os conjuntos 1 2 e 2 1 são iguais mas os pares ordenados 1 2 e 2 1 não são Seja n um inteiro positivo Mostre que em qualquer conjunto de n 1 inteiros existem pelo menos dois cujos restos são iguais quando divididos por n PROBLEMA PRÁTICO 10 Dado que 2x y x y 7 1 encontre x e y PROBLEMA PRÁTICO 11 Seja S 3 4 Liste todos os pares ordenados x y de elementos de S OPERAÇÕES BINÁRIAS E UNÁRIAS OPERAÇÕES BINÁRIAS E UNÁRIAS Para que seja uma operação unária em um conjunto S x tem que estar bem definida para todo x em S e S tem que ser fechado em relação a em outras palavras qualquer que seja x S x existe é único e pertence a S Não teremos uma operação unária se qualquer dessas condições falhar EXEMPLO 12 Defina x por x x de modo que x é o negativo de x Então é uma operação unária em ℤ mas não em ℕ pois ℕ não é fechado em relação a EXEMPLO 13 O conectivo lógico de negação é uma operação unária no conjunto das fbfs propositonais Se P é uma única fbf proposicional então P9 é uma única fbf proposicional OPERAÇÕES BINÁRIAS E UNÁRIAS PROBLEMA PRÁTICO 12 Quais das expressões a seguir não definem operações binárias nem unárias nos conjuntos dados Por que não a xy x y S conjunto de todos os inteiros positivos b xy x y S conjunto de todos os números racionais positivos c xy x S ℝ d xy máximo entre x e y S ℕ e x x S conjunto de todos os números reais positivos f x solução da equação x² x S ℂ Até agora todas as nossas operações binárias foram definidas por meio de uma descrição ou de uma equação Suponha que S é um conjunto finito S x₁ x₂ xₙ Então uma operação binária em S pode ser definida por uma tabela n n em que o elemento i j iésima linha e jésima coluna denota xᵢ xⱼ EXEMPLO 14 Seja S 2 5 9 e seja definida pela tabela Então 2 5 2 e 9 2 5 Inspecionando a tabela vemos que é uma operação binária em S OPERAÇÕES EM CONJUNTOS Podemos usar diagramas de Venn assim chamados em honra ao matemático britânico do século XIX John Venn para visualizar as operações binárias de união e interseção As áreas sombreadas nas Figuras 41 e 42 ilustram os conjuntos que resultam dessas operações binárias nos dois conjuntos dados OPERAÇÕES EM CONJUNTOS OPERAÇÕES EM CONJUNTOS PROBLEMA PRÁTICO 15 Ilustre A B em um diagrama de Venn OPERAÇÕES EM CONJUNTOS Dois conjuntos A e B tais que A B Ø são ditos disjuntos Então A B e B A por exemplo são conjuntos disjuntos EXEMPLO 18 Sejam A x x é um inteiro por não negativo B x yy ℕ e x 2y 1 C x yy ℕ e x 4y subconjuntos de ℕ Como B representa o conjunto dos inteiros ímpares não negativos A e B são conjuntos disjuntos Além disso todo inteiro não negativo é par ou ímpar de modo que A B ℕ Esses dois fatos também nos dizem que A B Todo múltiplo de 4 é um número par logo C é um subconjunto de A e portanto A C A C é de fato um subconjunto próprio de A e A C x yy ℕ x 4y 2 OPERAÇÕES EM CONJUNTOS PROBLEMA PRÁTICO 16 Sejam A 1 2 3 5 10 B 2 4 7 8 9 C 5 8 10 subconjuntos de S 1 2 3 4 5 6 7 8 9 10 Encontre a A B b A C c B C A C OPERAÇÕES EM CONJUNTOS IDENTIDADES ENVOLVENDO CONJUNTOS IDENTIDADES ENVOLVENDO CONJUNTOS EXEMPLAR 19 Vamos provar a identidade 3a Poderíamos desenhar diagramas de Venn para cada termo da equação e verificar que são iguais No entanto a identidade 3a é suposta de ser válida para quaisquer subconjuntos A B e C e qualquer desenho que fizermos não será inteiramente geral Assim se desenharmos A e B disjuntos isso não cobre o caso em que A e B são disjuntos Para se provar alguma coisa por meio de diagramas de Venn é preciso fazer uma figura para cada caso e quanto mais conjuntos estiverem envolvidos A B e C neste problema mais casos teremos Para evitar desenhar uma figura para cada caso vamos provar a igualdade entre os conjuntos mostrando a inclusão em ambas as direções Queremos então provar que A B C A B A C e que A B A C A B C IDENTIDADES ENVOLVENDO CONJUNTOS IDENTIDADES ENVOLVENDO CONJUNTOS EXERCÍCIOS CONJUNTOS EXERCÍCIOS 54 Sejam A x x é uma palavra que aparece antes de dado em um dicionário de português B x x é uma palavra que aparece depois de canário em um dicionário de português C x x é uma palavra com mais de quatro letras Quais das proposições a seguir são verdadeiras a B C b A B x x é uma palavra em um dicionário de português c cão B C d bambu A B CONJUNTOS 58 Considere os seguintes subconjuntos do conjunto de todos os estudantes A o conjunto de todos os estudantes de ciência da computação B o conjunto de todos os estudantes de física C o conjunto de todos os estudantes de matemática D o conjunto de todas as estudantes mulheres Usando as operações definidas nos conjuntos descreva cada um dos conjuntos a seguir em termos de A B C e D a o conjunto de todos os homens que não são estudantes de física b o conjunto de todos os estudantes de matemática que não são de ciência da computação c o conjunto de todos os estudantes que são mulheres ou que estudam matemática d o conjunto de todos os estudantes de matemática que não estudam ciência da computação nem física EXERCÍCIOS 82 A e B são subconjuntos de um conjunto S Prove as seguintes identidades mostrando a inclusão dos conjuntos em cada direção a A B A B Leis de De Morgan b A B A B c A B A A d A B B A B e A A A B A f A B C A B C EXERCÍCIOS 86 A B e C são subconjuntos de um conjunto S Prove as identidades a seguir usando as identidades demonstradas anteriormente inclusive as dos Exercícios 82 a 84 Justifique cada passo a A B A A b A B C A C B C c A A B A B d A B A B A B B A CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONJUNTOS CONTÁVEIS E NÃO CONTÁVEIS CONTAGEM A combinatória é o ramo da matemática que trata de contagem Problemas de contagem são importantes sempre que temos recursos finitos quanto espaço de armazenamento determinado banco de dados usa quantos usuários determinada configuração de computador pode suportar ou quando estamos interessados em eficiência quantos cálculos são efetuados por determinado algoritmo Problemas de contagem se resumem muitas vezes em determinar o número de elementos em algum conjunto finito ou seja qual é a cardinalidade do conjunto PRICÍPIO DA MULTIPLICAÇÃO EXEMPLO 24 Uma criança pode escolher uma entre duas balas uma rosa e outra preta e um entre três chicletes um amarelo outro verde e outro branco Quantos conjuntos diferentes a criança pode ter Podemos resolver este problema separando a tarefa de escolha dos doces em duas etapas sequenciais escolher primeiro a bala e depois o chiclete A árvore na Figura 43 mostra que existem 2 3 6 possibilidades R A R V R B P A P V e P B PRICÍPIO DA MULTIPLICAÇÃO Neste problema a sequência dos eventos poderia ser trocada a criança poderia escolher primeiro o chiclete e depois a bala resultando na árvore da Fig 44 mas o número de possibilidades é o mesmo 3 2 6 Pensar em uma sequência de eventos sucessivos nos ajuda a resolver o problema mas a ordem da sequência não faz parte do problema pois o conjunto R A é igual ao conjunto A R Essas duas árvores são balanceadas no sentido de que o segundo nível tem um número fixo de possibilidades independentemente dos resultados no nível anterior PRINÍCIPIO DA MULTIPLICAÇÃO Se existirem n₁ resultados possíveis para um primeiro evento e n₂ para um segundo então existirão n₁ n₂ resultados possíveis para a sequência dos dois eventos EXEMPLO 25 A última parte do seu número de telefone contém quatro dígitos Quantos desses números de quatro dígitos existem Podemos construir números de quatro dígitos através de uma sequência de tarefas escolher o primeiro dígito depois o segundo depois o terceiro e finalmente o quarto O primeiro dígito pode ser qualquer um dos 10 dígitos de 0 a 9 de modo que há 10 possibilidades para a primeira tarefa Da mesma forma existem 10 escolhas diferentes possíveis para cada um do segundo terceiro e quarto dígitos Usando o princípio da multiplicação simplesmente multiplicamos o número de possibilidades para cada tarefa na sequência Portanto existem 10 10 10 10 10000 números diferentes Se um elemento não puder ser usado de novo ou seja se não forem permitidas repetições o número de possibilidades será afetado EXEMPLO 26 Com relação ao Exemplo 25 quantos números de quatro dígitos existirá se um mesmo dígito não puder ser repetido Novamente temos uma sequência de tarefas para selecionar os quatro dígitos só que agora não podemos ter repetições Temos 10 possibilidades para o primeiro dígito mas apenas 9 para o segundo já que não podemos escolher um dígito igual ao primeiro e assim por diante Existem 10 9 8 7 5040 números diferentes PROBLEMA PRÁTICO 22 Se um homem tem quatro ternos oito camisas e cinco gravatas de quantas maneiras diferentes ele pode se vestir PRINÓCIPIO DA ADIÇÃO Suponha que queremos selecionar uma sobremesa entre três tortas e quatro bolos De quantas maneiras isso pode ser feito Temos dois eventos um com três resultados possíveis a escolha de uma torta e outro com quatro a escolha de um bolo No entanto não temos uma sequência de dois eventos aqui já que só comeremos uma sobremesa que será escolhida dentre as possibilidades de dois conjuntos disjuntos O número de escolhas possíveis é o número total de escolha que temos 3 4 7 Isso ilustra o princípio da adição PRINÓCIPIO PRINÓCIPIO DA ADIÇÃO Se A e B forem eventos disjuntos com n₁ e n₂ resultados possíveis respectivamente então o número total de possibilidades para o evento A ou B será n₁ n₂ PRINÓCIPIO DA ADIÇÃO EXEMPLO 30 Um consumidor deseja comprar um veículo de uma concessionária A concessionária tem 23 automóveis e 14 caminhões em estoque Quantas escolhas possíveis o consumidor tem O consumidor pode escolher um carro ou um caminhão Esses são eventos disjuntos a escolha de um carro tem 23 possibilidades e a de um caminhão 14 Pelo princípio da adição a escolha de um veículo tem 23 14 37 possibilidades Note a condição necessária de que os eventos A e B sejam conjuntos disjuntos Assim se um consumidor desejasse comprar um veículo de uma concessionária com 23 automóveis 14 caminhões e 17 veículos vermelhos em estoque não poderíamos concluir que o consumidor tem 23 14 17 escolhas LEMBRETE Use o princípio da adição só quando os eventos forem disjuntos não há resultados em comum EXEMPLO 32 Se A e B são conjuntos finitos então e Para provar a primeira identidade note que A B A B A B A B A B B A S A de modo que A A B A B A B A B ou A B A A B A segunda equação segue da primeira já que se B A então A B B Com referência ao Exemplo 24 suponha que queremos encontrar de quantas maneiras diferentes a criança pode escolher o doce em vez do número de conjuntos de doces que ela pode ter Então escolher uma bala rosa e depois um chiclete amarelo não é a mesma coisa que escolher primeiro um chiclete amarelo e depois uma bala rosa Podemos considerar dois casos disjuntos a escolha de balas ou de chicletes primeiro Cada um desses casos pelo princípio da multiplicação tem seis possibilidades de modo que pelo princípio da adição existem 6 6 12 maneiras diferentes de escolher os doces Quantos números de quatro dígitos começam com 4 ou 5 Podemos considerar dois casos disjuntos os números que começam com 4 e os que começam com 5 Contando os que começam com 4 há uma escolha possível para o primeiro dígito e 10 escolhas possíveis para cada um dos outros três dígitos Logo pelo princípio da multiplicação existem 1 10 10 10 1000 maneiras de se obter um número com quatro dígitos começando com 4 O mesmo raciocínio mostra que existem 1000 maneiras de se obter um número com quatro dígitos começando com 5 Pelo princípio da adição existem 1000 1000 2000 possibilidades ao todo Quantos inteiros de três dígitos números entre 100 e 999 inclusive são pares Uma solução se baseia no fato de que os números pares terminam em 0 2 4 6 ou 8 Considerando esses casos separados o número de inteiros com três dígitos terminando em 0 pode ser encontrado escolhendose os três dígitos sucessivamente Existem 9 escolhas de 1 a 9 para o primeiro dígito 10 escolhas de 0 a 9 para o segundo e uma escolha 0 para o terceiro Pelo princípio da multiplicação existem 90 números terminando em 0 Analogamente existem 90 números terminando em 2 em 4 em 6 e em 8 de modo que pelo princípio da adição existem 90 90 90 90 90 450 números Outra solução é devida ao fato de que existem apenas 5 escolhas para o terceiro dígito Pelo princípio da multiplicação existem 9 10 5 450 números Para esse problema existe uma terceira solução do tipo acidente feliz que discutimos na Seção 21 Existem 999 100 1 900 inteiros com três dígitos Como metade é par e metade é ímpar 450 têm que ser pares ÁRVORES DE DECISÃO Árvores como as das Figuras 43 e 44 ilustram o número de possibilidades de um evento baseado em uma série de escolhas possíveis Tais árvores são chamadas de árvores de decisão Árvores de decisão menos regulares ainda podem ser usadas para resolver problemas de contagem em que o princípio de multiplicação não se aplica EXEMPLO 39 António está jogando moedas Cada jogada resulta em cara C ou coroa K Quantos resultados possíveis ele pode obter se jogar cinco vezes sem cair duas caras consecutivas A Figura 45 mostra a árvore de decisão para esse problema Cada jogada da moeda tem dois resultados possíveis o ramo da esquerda está marcado com um C denotando cara e o da direita com um K denotando coroa Sempre que aparecer um C o próximo nível só poderá conter um ramo à direita K Existem 13 possibilidades que aparecem na parte inferior da árvore PROBLEMA PRÁTICO 25 Desenhe uma árvore de decisão para o número de cadeias formadas com os símbolos X Y e Z de comprimento 3 que não contenham Z imediatamente após Y 22 Uma comida que tem muita saída em lanchonetes no Havai é loco moco inventada em um restaurante em Hilo Ela consiste em um ovo em cima de uma carne em cima de uma porção de arroz tudo regado ao molho pardo O ovo pode ser frito mexido ou quente a carne pode ser hambúrguer mistura enlatada de carne e presunto linguiça bacon peru salsicha de cachorroquente salmão ou mahi o arroz pode ser branco ou integral Quantos locos mocos diferentes podem ser pedidos CONTAGEM PRÍNCIPIO DE INCLUSÃO E EXCLUSÃO PRÍNCIPIO DE INCLUSÃO E EXCLUSÃO Um pesquisador de opinião pública entrevistou 35 eleitores todos apoiando o referendo 1 o referendo 2 ou ambos e descobriu que 14 eleitores apoiam o referendo 1 e 26 apoiam o referendo 2 Quantos eleitores apoiam ambos Se denotarmos por A o conjunto dos eleitores que apoiam o referendo 1 e por B o conjunto dos eleitores que apoiam o referendo 2 sabemos que A B35 A14 B26 A BABA B 351426A B A B1426355 A Equação 2 pode ser estendida facilmente a três conjuntos da seguinte maneira A B CA B C AB CA B C ABCB CA CA BA B C Portanto a versão do princípio de inclusão e exclusão para três conjuntos é A B CABCA BA CB CA B C Além do argumento formal para se obter a Equação 3 a Figura 47 sugere uma espécie de argumento geométrico para A B C Quando somamos ABC estamos contando cada elemento em A B A C e B C duas vezes de modo que devemos retirar cada um deles uma vez Quando somamos ABC estamos contando cada elemento em A B C três vezes mas ao subtrair A B A C e B C eliminamos três vezes esses elementos logo precisamos colocálos de volta uma vez Um grupo de estudantes está planejando encomendar pizzas Se 13 comem linguiça calabresa 10 comem salame italiano 12 comem queijo extra 4 comem tanto calabresa quanto salame 5 comem tanto salame quanto queijo extra 7 comem tanto linguiça calabresa quanto queijo extra e 3 comem de tudo quantos estudantes tem o grupo Sejam A estudantes que comem linguiça calabresa B estudantes que comem salame italiano C estudantes que comem queijo extra Então A 13 B 10 C 12 A B 5 A C 7 e B C 3 Da Equação 3 A B C 13 10 12 5 7 3 22 Também poderíamos resolver esse problema colocando todas as informações em um diagrama de Venn Começando da parte mais de dentro para fora sabemos que existem 3 pessoas em A B C Figura 48a Sabemos também o número de pessoas em cada um dos conjuntos A B A C e B C de modo que com um pouco de subtração podemos preencher mais partes Figura 48b Conhecemos também o tamanho de A B e C o que nos permite completar a figura Figura 48c O número total de estudantes 22 é obtido somandose todos os números Na Equação 2 somamos o número de elementos dos conjuntos dados e subtraímos o número de elementos na interseção dos dois conjuntos Na Equação 3 somamos o número de elementos dos conjuntos dados subtraímos o número de elementos nas interseções de dois conjuntos e somamos o número de elementos na interseção dos três conjuntos Isso parece sugerir um padrão se tivermos n conjuntos devemos somar o número de elementos dos conjuntos dados subtrair o número de elementos nas interseções de dois conjuntos somar o número de elementos nas interseções de três conjuntos subtrair o número de elementos nas interseções de quatro conjuntos e assim por diante Isso nos leva à forma geral do princípio de inclusão e exclusão O princípio das casas de pombo adquiriu esse nome exótico da seguinte ideia se mais de k pombos entram em k casas de pombos então pelo menos uma casa vai ter mais de um pombo Embora isso pareça óbvio podemos aprofundar esse ponto Suponha que cada casa contenha no máximo um pombo Então existem no máximo k pombos e não os mais de k pombos que supostamente entraram nas casas Vamos agora enunciar o princípio das casas de pombo de uma forma menos pitoresca Se mais de k itens são colocados em k caixas então pelo menos uma caixa contém mais de um item PRICÍPIO DAS CASAS DE POMBO PRICÍPIO DAS CASAS DE POMBO EXERCÍCIOS Quantas cartas devem ser retiradas de um baralho padrão com 52 cartas para se obter com certeza duas cartas do mesmo naipe