Demonstrações com Indução Matemática

b Mostre que P1 é verdadeira completando o passo base da demonstração a Qual é a hipótese indutiva d O que você precisa demonstrar no passo de indução e Complete o passo de indução f Explique por que esses passos mostram que esta fórmula é verdadeira sempre que n for um número inteiro positivo 5 Demonstre que 1² 2² 3² 2n 1² n 12n 3 sempre que n for um número inteiro não negativo 9 Demonstre que 11 12 21 n n 1 1 sempre que n for um número inteiro positivo 11 Encontre uma fórmula para 1 12 13 1n examinando os valores desta expressão para pequenos valores de n 12 Demonstre que k² nn 12n 16 15 Demonstre que para todo número inteiro positivo n 1 2 3 n nn 12 19 Considere Pn como a proposição de que 1 14 19 1n² 1n em que n é um número inteiro maior que 1 a Qual é a proposição P2 b Mostre que P2 é verdadeira completando o passo base da demonstração c Qual é a hipótese indutiva d O que você precisa demonstrar o passo de indução e Complete o passo de indução f Explique por que esses passos mostram que a inéquação é verdadeira sempre que n for um número inteiro maior que 1 33 Demonstre que 5 divide n³ n sempre que n for um número inteiro não negativo 36 Demonstre que 2ⁿ 1 divísivel por 8 sempre que n for um número inteiro positivo e ímpar 37 Demonstre que se n for um número inteiro positivo então 133 divide 11 12 53 Reguer cálculo Use a indução matemática para demonstrar que a derivada dfx xn igual a xn1 sempre que n for um número inteiro positivo 62 Use a propriedade da boa ordenação para mostrar que a b 0 é demonstrado válido P1 e P2 são verdadeiras 67 Demonstre que gn 2n para n 2 69 Mostre que i₁ i₂ iₙ para um grupo de intervalos abertos de números reais n é de um intervalo não vazio ou seja se 1 n iₙ então a interseção de todos os conjuntos iₖ não vazio ou seja I₁ I₂ Iₙ não vazio 33 Demonstre que 5 divide n5 n sempre que n for um número inteiro não negativo 34 Demonstre que 6 divide n3 n sempre que n for um número inteiro não negativo 35 Demonstre que n2 1 divisorível por 8 sempre que n for um número inteiro positivo e ímpar 36 Demonstre que 2 elevado a 4n 5n 1 sempre que n for um número inteiro positivo 37 Demonstre que se for um número inteiro positivo então 133 divide 11n 12n 38 Use a indução matemática nos exercícios 38 e 46 para demonstrar os resultados do conjuntos 39 Demonstre que se A1 A2 An e B1 B2 Bm forem conjuntos tal que A1 e B1 para i 1 2 n então U Ai U Bi para i 1 2 n 40 Demonstre que se A1 A2 An e B forem conjuntos então A1 A2 An B A B A1 A2 An 41 Demonstre que se A1 A2 An e B forem conjuntos então A1 A2 An A B A1 A2 An B 42 Demonstre que se A1 A2 An e B forem conjuntos então A1 B A2 B A1 An B 43 Demonstre que se A1 A2 An forem subconjuntos de um conjunto universo U então U k U k 44 Demonstre que se A1 A2 An forem conjuntos então A1 B A2 An B A1 A2 An B 45 Demonstre que um conjunto com n elementos tem n 12 subconjuntos contendo elementos sempre que n for um número inteiro maior que ou igual a 2 46 Demonstre que um conjunto com n elementos tem n 26 subconjuntos que são elementos sempre que um número inteiro maior que ou igual a 3 47 O exercícios 47 a 49 apresentam demonstrações incorretas no uso da indução matemática Você precisaria identificar em cúal exercício 48 O que está errado nesta demonstração que todos os cavalos adoecem da mesma cor Passo Pn como a proposição de que todos os cavalos em um conjunto de n cavalos são da mesma cor 53 Reguer cálculos Use a indução matemática para demonstrar que a derivada dfx x5 x4 x1 sempre que for um número inteiro positivo Passo para o passo de indução use a regra do produto para derivadas 54 Suponha que A e B sejam matrizes quadradas com a propriedade AB BA Mostre que ABn BAn para todo número inteiro positivo n 55 Suponha que n seja um número inteiro positivo Use a indução matemática para demonstrar que a não b forem números inteiros como b b mod m então a a b para um número não negativo 56 Use a indução matemática para mostrar que v1 v2 p1 vP equivalem a p1 p2 pn sempre que P1 P2 Pn forem proposições 57 P1 P1 P2 P2 P3 P1 P1 P3 P2 A1 P2 A2 A2 p1 sempre que houver uma tautologia sempre que n 3 foram proposições quem P 2 58 Mostre que retas espaciais no plano em x2 y2 2 21 considerando nenhuma dessas retas passam por um ponto 59 Considere a1 a2 an como números positivos A média aritmética desses números é definida por A a1 a2 an n e a média geométrica desses números é definida por G a2a1 an1n Use a indução matemática para demonstrar que A G 60 Use a indução matemática para demonstrar o Lema 2 da Seção 3 onde estabelece que se p é um número primo p1 p1 a2 a2 então A 2 para algum número inteiro n 61 Mostre que se n for um número inteiro positivo então 1a1 ak n 42 Indução Completa e Boa Ordenação PASSO DE INDUÇÃO Para a hipótese indutiva assumimos que 2T2h 1 sempre que T1 e T2 form árvores binárias completas Pelas fórmulas recursivas para nT e T temos que nT 1 nT1 nT2 e hT1 hT2 Verificamos que nT 1 nT1 nT2 pela fórmula recursiva para nT 1 2T2h 1 2T2h 1 1 pela hipótese indutiva 2 max2T1 2h2 1 1 porque max2 2max2 Isso completa o passo de indução Indução Generalizada Podemos estender a indução matemática para demonstrar os resultados de outros conjuntos que têm a propriedade da boa ordenação além do conjunto dos números inteiros Discutimos este conceito em detalhes na Seção 86 mas daremos alguns exemplos aqui para ilustrar esses aproximações Como exemplo note que podemos definir uma ordem de N x N os pares ordenados dos números inteiros não negativos especificando que x1 y1 é menor que o igual a x2 y2 se x1 x2 ou x1 y1 x2 e y1 y2 isto é chamado de ordem lexicográfica Organização Se n 1 então a2 a 2 2 Portanto devemos maçã conforme aproximadamente a soma de assentos e assembleias será 1 Se um termo a de nn 2n acontece na prática do valor inicial de um polinômio INDICAÇÃO COMPLETA Para demonstrar que Pn é verdadeira para todos os números inteiros positivos n em que Pn é uma função proposicional completamos dois passos PASSO BASE Verificamos que a proposição P1 é verdadeira PASSO DE INDUÇÃO Mostramos que a proposição condicional Pk P2 Pk Pk 1 é verdadeira para todos os números inteiros positivos k PASSO BASE O passo base dessa demonstração é válido aqui simplesmente é verificado que nós podemos alcançar o primeiro degrau TENTATIVA DE PASSO DE INDUÇÃO A hipótese indutiva é a proposição que afirma que podemos alcançar o késimo degrau da escada Para completar o passo de indução precisamos mostrar que se assumirmos a hipótese indutiva para n inteiro positivo k se podemos alcançar o k 1ésimo degrau da escada Entretanto não existe uma forma óbvia de completar esse passo de indução porque não sabemos a partir do késimo grau Além disso sabemos apenas que se podemos alcançar um grau podemos alcançar também dois degraus acima PASSO BASE P2 é verdadeira porque 2 pode ser escrito como o produto de um número primo ele mesmo Note que P2 é o primeiro caso que precisamos estabelecer PASSO BASE Verificamos que as proposições Pb Pb 1 Pb j são verdadeiras Como completamos o passo base e o de indução da demonstração por indução completa sabemos por esta indução que Pn é verdadeira para todos os números inteiros n com n 12 FIGURA 2 Triangulações de um Polígono FIGURA 3 Construindo uma Diagonal Interna de um Polígono Simples Exemplos Extras b Demonstre sua resposta de a usando o princípio da indução matemática Certifiquese de afirmar explicitamente sua hipótese indutiva no passo de indução 9 Use a indução completa para demonstrar que 2 é um número irracional Dica Considere Pn como a proposição de que 2 nb para qualquer número inteiro positivo bn 15 Prove que o primeiro jogador tem uma estratégia vencedora para o jogo Chomp introduzindo no Exemplo 17 se o quadrado inicial for quadrado Dica Use a indução completa para mostrar que esta estratégia funciona FIGURA 1 Uma Ilustração Definida Recursivamente encontrados a partir de termos anteriores podemos usar a indução para demonstrar os resultados da sequência Podemos definir um conjunto recursivamente especificando alguns elementos iniciais em um passo base e fornecendo uma regra para a construção de novos elementos a partir daqueles obtidos no passo recursivo Para demonstrar os resultados de recursividade em conjuntos usamos um método chamado de indução estrutural ou recursão Solução A partir da definição recursiva temos que f1 2f0 3 23 3 9 f2 2f1 29 3 21 f3 2f2 321 3 45 f4 2f3 345 3 93 Muitas funções podem ser estudadas usando suas definições recursivas A função fatorial é uma delas EXEMPLO 2 Dê uma definição recursiva da função fatorial Fn n Solução Podemos definir a função fatorial especificando seu valor inicial ou seja F0 1 e dando uma regra para encontrar Fn 1 a partir de Fn Isso é obtido notando que n 1 é computado a partir de n multiplicado por n 1 Assim a regra desejada é Fn 1 n 1Fn Solução A primeira parte da definição recursiva é ak a0 A segunda parte é k0n1 ak k0n ak an1 Em algumas definições recursivas de funções os valores da função dos primeiros k números inteiros positivos são especificados e uma regra é dada para determinar o valor da função para números inteiros maiores a partir de seus valores para alguns ou todos os números inteiros precedentes Essas definições recursivas são fixadas dessa maneira para produzir funções bem definidas a partir da indução completa veja o Exercício 57 no final desta seção PASSO DE INDUÇÃO Assuma que Pk seja verdadeira ou seja que fα2 para todos os números inteiros com 3 j k em que k 2 Devemos mostrar que Pk 1 é verdadeira ou seja que fαk1 0 Como α é uma solução de x2 x 1 0 como a fórmula quadrática mostra temos que α2 α 1 Assim αk1 αk αk1 α αk3 Pela hipótese indutiva se k 2 temos que fk αk3 fk1 αk2 Assim temos fk1 fk fk1 αk2 αk3 αk1 Temos que Pk 1 é verdadeira Isso completa a demonstração Lembrese O passo de indução mostra que sempre que k 4 Pk 1 é dado a partir da hipótese de que Pk seja verdadeira para 3 j k Assim esse passo não mostra que P3 P4 Além disso mostramos que P4 é verdadeira separadamente Podemos agora mostrar que o algoritmo de Euclides usa Olog b divisões para encontrar o máximo divisor comum dos números inteiros positivos a e b em que a b TEOREMA 1 TEOREMA DE LAMÉ Considere a e b como números inteiros positivos com a b Então o número de divisões utilizado pelo algoritmo de Euclides para encontrar mdca b é menor que ou igual a cinco vezes o número de dígitos decimais em b Demonstração Lembrese de que quando o algoritmo de Euclides é aplicado para encontrar o mdca b com a b esta sequência de equações em que a r₀ e b r₁ é obtida r₁ r₀ mod r₁ r₂ r₁ mod r₂ r₁ r₂ r₃ f₃ Temos que se n divisões forem usadas pelo algoritmo de Euclides para encontrar mdca b com a b então b f₁₁ A partir do Exemplo 6 sabemos que f₁₁ α1 para n 2 em que α 1 52 Assim temos que b α1 Além disso como f₁₁ α1 15 temos que logbn 1 log10 a n 15 Assim n 1 5 log10 a Agora suponha que b tenha k dígitos decimais Então b 10k e log10 b k Temos que n 1 k e como k n 5k Isso finaliza a demonstração EXEMPLO 7 Considere o subconjunto S do conjunto dos números inteiros definido por PASSO BASE 3 S PASSO RECURSIVO Se x S e y S então x y S Os novos elementos encontrados em S são 3 pelo passo base 3 3 6 na primeira aplicação do passo recursivo 3 6 6 6 12 na segunda aplicação do passo recursivo e assim por diante Mostraremos depois que S é o conjunto dos múltiplos positivos de 3 As definições recursivas desempenham importante papel no estudo de cadeias Veja o Capítulo 12 para uma introdução da teoria das linguagens formais por exemplo Lembrese da Seção 24 em que uma cadeia de um alfabeto Σ é uma sequência finita de símbolos de Σ Podemos definir Σ o conjunto das cadeias sobre Σ recursivamente como mostra a Definição 2 PASSO BASE ϵ Σ em que ϵ é a cadeia vazia que não contém símbolos PASSO RECURSIVO Se w Σ e x Σ então wx Σ O passo base da definição recursiva de cadeias diz que a cadeia vazia pertence a Σ O passo recursivo afirma que novas cadeias são produzidas pela adição de um símbolo a partir de Σ ao final das cadeias em Σ Em cada aplicação do passo recursivo cadeias com símbolo adicional são geradas EXEMPLO 9 Comprimento de uma Cadeia De uma definição recursiva de lw o comprimento ou a extensão da cadeia w Solução A extensão de uma cadeia pode ser definida por lλ 0 lwx lw 1 se w Σ e x Σ Outro uso importante das definições recursivas é definir fórmulas bem formadas de vários tipos Isso é ilustrado nos exemplos 10 e 11 DEFINIÇÃO 4 O conjunto de árvores com raiz em que uma árvore com raiz consiste em um conjunto de vértices que contém um vértice distinto chamado de raiz e arestas que conectam esses vértices pode ser definido recursivamente por estes passos PASSO BASE Um único vértice r é uma árvore com raiz PASSO RECURSIVO Suponha que T1 T2 Tn são árvores com raízes disjuntas que possuem raízes r1 r2 rn respectivamente Então o gráfico formado começando com uma raiz r que não esteja em nenhuma das árvores com raízes T1 T2 Tn e adicionando uma aresta a partir de r a cada um dos vértices r1 r2 rn também uma árvore com raiz DEFINIÇÃO 6 O conjunto das árvores binárias completas pode ser definido recursivamente pelos passos abaixo PASSO BASE Há uma árvore binária completa que contém apenas um único vértice r PASSO RECURSIVO Se T1 e T2 forem árvores binárias completas disjuntas haverá uma árvore binária completa indicada por T1 T2 que consiste em uma raiz r junto com as arestas que ligam a raiz a cada uma das raízes das subárvores à esquerda T1 e à direita T2 Passo basePasso 1Passo 2 Exemplos de demonstrações que usam a indução estrutural A indução estrutural pode ser usada para demonstrar que todos os membros de um conjunto construídos recursivamente têm uma propriedade particular Definimos recursivamente a altura hT de uma árvore binária completa T Passo base A altura da árvore binária completa T com apenas uma raiz h0 0 Dê uma definição recursiva para cada um dos conjuntos de pares ordenados de números inteiros positivos abaixo Dê uma definição recursiva para cada um dos conjuntos de pares ordenados de números inteiros positivos de forma correta O conjunto dos valores abaixo da função de Ackermann Os exercícios 60 a 62 lidam com iterações da função logarítmica Considere log n como o logaritmo de n na base 2 A função logkn é definida recursivamente por logkn loglogk1n e log0n n definido caso contrário O logaritmo iterado é a função log n cujo valor em n é 0 em número inteiro não negativo k tal que logk n 1 ALGORITMO 1 Um Algoritmo Recursivo para Computar n procedure fatorialn número inteiro não negativo if n 0 then fatorialn 1 else fatorialn n fatorialn 1 O Exemplo 2 mostra como um algoritmo recursivo pode ser construído para avaliar uma função a partir de sua definição recursiva ALGORITMO 3 Potenciação Modular Recursiva procedure mpotencialb h números inteiros com b 2 n 0 if n 0 then mpotencialb n 1 else if n mod 2 0 then mpotencialb n mpotencialb n22 mod m else mpotencialb n mpotencialb n2 mod m b mod m EXEMPLO 5 Expresse o algoritmo de busca linear como um procedimento recursivo Solução Para a busca por x na sequência de busca a1 a2 an no iésimo passo do algoritmo r e x são comparados Se x for igual a ai então i é a localização de x Por outro lado a busca x é reduzida a uma busca em uma sequência com um elemento a menos ou seja a sequência a1 an Podemos agora fornecer um procedimento recursivo que está apresentado em pseudocódigo no Algoritmo 5 Considere a busca i j x como o procedimento que procura por x na sequência a1 a2 aj A entrada do algoritmo consiste no trio 1 n x O procedimento termina em um passo se o primeiro termo da sequência restante for x ou se houver termos adicionais o mesmo procedimento é realizado mas como uma sequência de busca com um termo a menos obtendose o primeiro termo da sequência de busca ALGORITMO 5 Um Algoritmo de Busca Linear Recursivo procedimento buscai j x números inteiros 1 i n 1 j n if ai x then localizacao i else if x ai then localizacao 0 else buscai 1 j x EXEMPLO 6 Construa uma versão recursiva do algoritmo de busca binária Solução Suponha que queiramos localizar x na sequência a1 a2 an números inteiros em ordem crescente Para realizar uma busca binária começamos pela comparação de x com o termo do meio am l h2 Nosso algoritmo terminará se x for igual a este termo Por outro lado reduzimos a busca a uma sequência de busca menor ou seja a primeira metade da sequência se x for menor que o termo do meio da sequência original ou a segunda metade se ele for maior Reduzimos a solução do problema de busca para a solução do mesmo problema com uma sequência aproximadamente igual a metade da original Expressamos esta versão recursiva do algoritmo de busca binária como Algoritmo 6 ALGORITMO 6 Um Algoritmo de Busca Binária Recursivo procedimento buscabinariai x l h números inteiros 1 i n 1 j n m l h2 if x am then localizacao m else if x am e i m 1 then buscabinariai x l m 1 else if x am e j m 1 then buscabinariai x m 1 h else localizacao 0 EXEMPLO 7 Demonstre que o Algoritmo 2 que computa potências de números reais está correto Solução Usamos a indução matemática no expoente n PASSO BASE Se n 0 o primeiro passo do algoritmo nos diz que potência a 0 1 Isso é correto porque a0 1 para todo número real diferente de zero Isto completa o passo base PASSO DE INDUÇÃO A hipótese indutiva é a proposição de que a potência a k ak para todo a 0 para o número inteiro não negativo k ou seja a hipótese indutiva é a proposição de que o algoritmo computará corretamente a Para completar o passo de indução mostramos que k 1 é a potência a k 1 a potênciaa k a ak ak 1 Isto completa o passo de indução Completemos os passos base e o de indução assim pela indução completa sabemos que o Algoritmo 2 está correto ALGORITMO 8 Um Algoritmo de Iteração para Computar Números de Fibonacci procedimento iteração de fibonaccin número inteiro não negativo if n 0 then y 0 else begin x 0 y 1 for i 1 to n 1 begin x x y y x end end FIGURA 2 A Merge Sort de 8 2 4 6 9 7 10 1 5 3 1 2 3 4 5 6 7 8 9 10 TABELA 1 Unindo Duas Listas Ordenadas 2 3 5 6 e 1 4 Primeira Lista Segunda Lista Lista Unida Comparação 2 3 5 6 1 4 1 2 2 3 6 4 1 2 4 3 5 4 12 3 4 5 6 4 123 4 5 5 6 4 123 4 1234 1 2 3 4 ALGORITMO 10 Unindo Duas Listas procedure mergeL₁ L₂ listas ordenadas L lista vazia while L₁ e L₂ não são vazias begin remoar o menor entre os primeiros elementos de L₁ e L₂ e coloqueo à direita em L if remover esse elemento torna uma lista vazia then remova todos os elementos da outra lista e insiraos em L end L é a lista unida com elementos em ordem crescente O número de comparações necessárias para a merge sort ordenar uma lista com n elementos é On log n Desenvolva um algoritmo recursivo para encontrar o nésimo termo da sequência definida por a₀ 1 a₁ 2 e aₙ aₙ₁ aₙ₂ para n 2 3 4 Visto que um programa incorreto pode levar a resultados desastrosos várias metodologias têm sido construídas para verificar programas Esforços têm sido feitos para automatizar a verificação de programas para os quais isso pode ser realizado por meio de um computador Entretanto ainda em progresso limitado foi alcançado nesse sentido De fato algumas matemáticas e teóricas além da computação argumentam que nunca será real a mecanização da demonstração para verificar a exatidão de programas complexos Alguns dos conceitos e métodos usados para demonstrar que os programas estão corretos serão introduzidos nesta seção Muitos métodos diferentes foram desenvolvidos para isso Discorrendo o método introduzido por Tony Hoare mas muitos outros foram desenvolvidos Além disso não vamos desenvolver uma metodologia completa para a verificação de programas neste livro O objetivo desta seção é apresentar uma breve introdução à área da verificação de programas juntamente com as regras de lógica as técnicas de demonstração e o conceito de algoritmo Suponha que o programa S tenha sido dividido nos subprogramas S₁ e S₂ Escreva S S₁ S₂ para indicar que S é constituído por S₁ seguido de S₂ Suponha que a exatidão de S₁ com relação a asserção inicial p e a final q e a exatidão de S₂ com relação às asserções estabelecidas Temos que se p for verdadeira e S₁ for executado e terminar então q é verdadeira e se p for verdadeira e S S₁ S₂ for executado e terminar então r é verdadeira Assim se p for verdadeira e S S₁ S₂ for executado pode ser estabelecido como pS₁q gS₂r EXEMPLO 2 Verifique se o segmento de programa if x y then y x está correto com relação à sua asseção inicial V e à sua asserção final y x Solução Quando a asserção inicial for verdadeira e x y a tarefa y x é realizada Assim a asserção final que determina que y x é verdadeira neste caso Além disso quando a asserção inicial for verdadeira e x y for falsa então ocorre x y a asserção final o novamente verdadeira Assim usando a regra de inferência para segmentos de programa deste tipo este programa está correto com relação às suas asserções inicial e final abs x Assim usando a regra de inferência para segmentos de programas deste tipo este segmento está correto com relação às assersões dadas inicial e final Laços Invariáveis Agora serão descritas as demonstrações de exatidão com laços enquanto while Para desenvolver uma regra de inferência para segmentos de programas deste tipo Por fim precisamos checar que o laço while termina de fato No começo do programa i é determinado com o valor 1 assim depois de n 1 laços o novo valor de i será n e o laço termina neste ponto Um exemplo final será apresentado para mostrar como as várias regras de inferência podem ser usadas para verificar a exatidão de um programa maior EXEMPLO 5 Demonstrar 3 Verifique que o segmento de programa x 2 z x y if y 0 then z z 1 else z 0 está correto com relação à asseração inicial V 3 e a final z 6 4 Verifique que o segmento de programa if x y then min x min y está correto com relação à asseração inicial V e a final x y min y ou x y min x 1 Use a indução matemática para mostrar que frac23 frac34 fracnn1 fracnn1 onde n é um número inteiro positivo 3 Use a indução matemática para mostrar que 1 cdot 20 2 cdot 21 3 cdot 22 n cdot 2n1 n12n 1 onde n é um número inteiro positivo 30 Requer cálculo Use a indução matemática a regra do produto para mostrar que se f1x f2x fkx forem funções diferenciáveis então f1xf2xfkx é diferenciável Suponha que A₁ A₂ Aₖ seja um grupo de conjuntos Suponha que R₂ A₄ e R₁ A₁ para k 3 4 Use a indução matemática para demonstrar que x R se somente se x pertencer a um número ímpar de conjuntos A₁ A₂ Aₖ Lembrese de que S T é a diferença simétrica dos conjuntos S e T definida na Seção 22 Encontre uma fórmula explícita para fn se f1 1 e fn n 1 2n 1 para n 2 Demonstre seu resultado usando indução matemática Mostre que uma cadeia de parênteses é balanceada se e somente se Nw 0 sempre que w for uma parentese válida ou seja w w Capítulo 5 Contagem Combinatória o estudo dos arranjos dos objetos é uma parte importante da matemática discreta Este assunto vem sendo estudado desde muitos anos antes do século XVII quando questões combinatórias apareceram no estudo de jogos A enumeracão contagem de objetos com certas propriedades é uma parte importante da combinatória Devese contar os objetos para resolver muitos tipos diferentes de problemas Por exemplo a contagem é usada para determinar a complexidade de algoritmos Ela também é exigida para determinar se há números de telefone ou endereços de protocolo da Internet suficientes para atender as necessidades REGRAS DO PRODUTO Suponha que um procedimento possa ser dividido em uma sequência de duas tarefas Se houver n₁ formas de fazer a primeira tarefa e para cada uma dessas formas de fazer a primeira tarefa há n₂ formas de fazer a segunda tarefa então há n₁n₂ formas de concluir o procedimento Solução Uma função corresponde a uma escolha de um dos n elementos no contradomínio para cada um dos m elementos do domínio Portanto pela regra do produto h nm funções partindose de um conjunto com m elementos para um conjunto com n elementos Por exemplo há 5 funções diferentes partindose de um conjunto com três elementos para um conjunto com cinco elementos O valor inicial de k é zero Cada vez que um laço é dado 1 é adicionado a k Considere Ti como tarefa de dar o iésimo laço Então o número de vezes que os laços são dados é o número de formas necessárias para realizar as tarefas T1 T2 Tm matemática não é o mesmo que escolher um estudante que é mestre em matemática porque nenhum deles é ao mesmo tempo um membro da faculdade e um mestre Então pela regra da soma temos que 37 83 120 maneiras possíveis de escolher esse representante Esta igualdade apenas se aplica quando os conjuntos em questão são disjuntos A situação é muito mais complicada quando esses conjuntos têm elementos em comum Número de Bits 0 1 2 3 4 8 16 Classe A netid hostid Classe B 0 0 netid hostid Classe C 1 1 0 netid Classe B 1 1 1 0 Endereço Multicast Classe E 1 1 1 1 Endereço FIGURA 1 Endereços de Internet IPv4 EXEMPLO 16 Contagem de Endereços da Internet Na Internet que é construída por redes de transmissão de computadores interconectadas fisicamente cada computador ou mais precisamente cada rede de transmissão conectada a um computador possui um endereço de Internet Na Versão 4 do Protocolo de Internet IPv4 agora em uso um endereço é uma cadeia de 32 bits Este comunica com um número de transmissão netid O netid é seguido do seguinte do número de hospedagem hostid que identifica um computador como um número que determina rede de transmissão EXEMPLO 17 Quantas cadeias de bits de extensão oito começam com 1 bit ou terminam com dois bits 00 Solução Podemos construir uma cadeia de bits de extensão oito que começa com um 1 bit ou termina com dois bits 00 construindo uma cadeia de bits de extensão oito que começa com um 1 bit ou construindo uma cadeia de bits de extensão oito que termina com dois bits 00 Podemos construir uma cadeia de bits que começa com 1 de 27 128 maneiras seguindo a regra do produto pois o primeiro bit pode ser escolhido de uma única maneira e com os outros seis bits podem ser escolhidos de duas formas Suponha que um telefone no futuro seja atribuído um número que contém um código de país de 1 a 3 dígitos ou seja a forma X XX ou XXX seguido do número de telefone com 10 dígitos na forma de número XXXNNNNNNNN Um estudante em uma aula de matemática discreta é do área de escolha da computação ou da matemática e das duas áreas Quantos estudantes há na sala de 38 graduados com ciência da computação Quantas funções parciais veja o preâmbulo do Exercício 73 na Seção 23 possíveis a partir de um conjunto com n elementos para um conjunto com m elementos onde m é um número inteiro positivo de 14 campos diferentes especificando muitas coisas incluindo a fonte e os endereços de destinatrário a área de dados que contêm os dados atuais que são transmitidos Um dos 14 campos de cabeçalho é o campo de cabeçalho estendido indicado por HLEN que é caracterizado pelo protocolo por ter 4 bits e especificar a extensão do cabeçalho em blocos de 32 bits Por exemplo se HLEN 0110 o cabeçalho é composto por seis blocos de 32 bits Outro componente dos 14 campos de cabeçalho é o campo de extensão total de 16 bits indicado por EXTENSÃO TOTAL que especifica a extensão em bits do todo datagrama inclusive a área de cabeçalho A extensão da área de dados e a extensão total do datagrama menos a extensão do cabeçalho O princípio da casa dos pombos é também chamado de Princípio das Gavetas de Dirichlet depois que o matemático alemão Dirichlet usou frequentemente este princípio em seu trabalho no século XIX O princípio da casa dos pombos pode ser usado para demonstrar diversas funções Uma função f de um conjunto com k 1 ou mais elementos para um conjunto com k elementos não é injetora A GENERALIZAÇÃO DO PRINCÍPIO DA CASA DOS POMBOS Se N objetos são colocados em k caixas então há pelo menos uma caixa com Nk objetos Usaremos uma demonstração por contradição Suponha que nenhuma das caixas tenha mais que Nk 1 objetos Então o número total de objetos é no máximo kNk 1 kNk 1 1 N em que a inequação Nk 1 foi usada Isto é uma contradição pois há um total de N objetos Suponha que haja quatro caixas uma para cada naipe e assim que as cartas forem sendo selecionadas elas são colocadas na caixa reservada para cada naipe Usando a generalização do princípio da casa dos pombos vemos que se N cartas são selecionadas há pelo menos uma caixa com no mínimo N4 cartas Consequentemente sabemos que pelo menos três cartas de um naipe são selecionadas se N4 3 O menor número inteiro N tal que N4 3 é N 2 4 1 9 então nove cartas são suficientes Note que se oito cartas forem escolhidas é possível que haja duas cartas de cada naipe então ainda necessitamos mais uma Consequentemente nove cartas devem ser selecionadas para garantir que pelo menos três cartas de um naipe sejam escolhidas Uma boa forma de pensar nisso é notar que depois da a votação está escolhida não há como evitar ter uma terceira carta de algum naipe Qual o menor número de códigos de área que serão necessários para garantir que os 25 milhões de telefones em estudo sejam determinados por números de telefone com 10 dígitos Considera que os números de telefone têm o formato XXXXXXXXXX em que os três primeiros dígitos são o código de área N representa um dígito entre 2 e 9 inclusive e X representa qualquer dígito Há oito milhões de números de telefone diferentes na forma XXXXXXX como sabemos pelo Exemplo 8 da Seção 51 Portanto pela generalização do princípio da casa dos pombos entre 25 milhões de telefones pelo menos 25 000 000 8 000 000 deles devem ter números idênticos Portanto pelo menos quatro códigos de área são necessários para assegurar que todos os números de 10 dígitos sejam diferentes Suponha que um laboratório de ciência da computação tenha 15 estações de trabalho e 10 servidores Um cabo pode ser usado para conectar diretamente uma estação a um servidor Para cada servidor apenas uma conexão direta a este servidor pode ser feita Queremos garantir que a qualquer hora qualquer conjunto de 10 ou menos estações de trabalho possa simultaneamente acessar servidores diferentes por meio de conexões diretas Embora possam fazer isso conectando cada estação diretamente a um servidor usando todos os 10 conexões qual é o número mínimo de conexões diretas necessárias para alcançar este objetivo Exercícios 5 Contagem 53 Permutações e Combinações Usaremos agora a regra do produto para encontrar a fórmula para Pn r sempre que n e r forem números inteiros positivos com 1 r n Se n e r são números inteiros com 0 r n então Pn r n n r O número de rcombinações de um conjunto com n elementos usando a fórmula para o número de rpermutacões de um conjunto 525 526 527 d Das 13 pessoas que apareceram três são mulheres Há quantas maneiras possíveis de escolher os 10 jogadores se pelo menos um desses jogadores deve ser sua mulher 54 Coeficientes Binomiais EXEMPLO 2 Qual é o desdobramento de x y² Solução A partir do binômio de Newton temos que x y² 2 kxᶱy²²ᶱ 2 2 1x² 1y² 4y⁴ x² 4xy 2y² 4xy y⁴ Demonstração Um conjunto com n elementos tem um total de 2ⁿ subconjuntos diferentes Cada subconjunto tem zero elementos um elemento dois elementos ou n elementos Há ⁿ k subconjuntos com nenhum elemento ⁿ 1 subconjuntos com um elemento ⁿ 2 subconjuntos com dois elementos e ⁿ n subconjuntos com n elementos Portanto ⁿ k0 ⁿ k é o número total de subconjuntos de um conjunto com n elementos Isto mostra que ⁿ k0 ⁿ k 2ⁿ COROLÁRIO 2 Consider e n como um número inteiro positivo Então ⁿ k0 1ᵏⁿ k 0 Demonstração Quando usamos o binômio de Newton com x 1 e y 1 vemos que 0 00 1 1ᵐ ⁿ k0 ⁿ k1ᵏ ⁿ k0 ⁿ k1ᵏ Isto demonstra o corolário Lembrese O Corolário 2 implica que ⁿ k0 ⁿ k ⁿ k4 ⁿ k ⁿ k5 ⁿ k TEOREMA 2 IDENTIDADE DE PASCAL Considere n e k como números inteiros positivos com n k Então n 1 k n k n k 1 Demonstração Suponha que T seja um conjunto com n 1 elementos Considere a como um elemento de T e considere S T a Note que n k subconjuntos de T com k elementos Entretanto um subconjunto de T com k elementos contém o juntamente com k 1 elementos de S ou contém k elementos de S e não contém a Visto que há n k 1 subconjuntos de S há ⁿ k subconjuntos de k elementos de T que não contêm a pois há ⁿ k subconjuntos k elementos de S Consequentemente n 1 k n k n k 1 Lembrese Mostramos uma demonstração combinatória da identidade de Pascal Também é possível demonstrar essa identidade pela manipulação algébrica a partir da fórmula para ⁿ k veja o Exercício 19 no final desta seção Lembrese A identidade de Pascal junto com as condições iniciais ⁰ 0 1 para todos os números inteiros n pode ser usada para definir recursivamente coeficientes binomiais FIGURA 1 Triângulo de Pascal Concluímos esta seção com demonstrações combinatórias de duas das muitas identidades dos coeficientes binomiais TEOREMA 3 IDENTIDADE DE VANDERMONDE Considere m n e r como números inteiros não negativos com r não excedente a m ou n Então m n r ⁿ k0 m kn r k Lembrese Esta identidade foi descoberta pelo matemático AlexandreThéophile Vandermonde no século XVIII Demonstração Suponha que haja m itens em um conjunto e r itens em um segundo conjunto Então o número total de maneiras de escolher r elementos da união desses conjuntos é m n r Outra maneira de escolher r elementos da união é escolher k elementos do primeiro conjunto e então selecionar r k elementos do segundo conjunto ou seja usar o regra do produto Assim o número total de maneiras é dado pelo m kn r k Isto demonstra a identidade de Vandermonde O Corolário 4 diz respeito à identidade de Vandermonde COROLÁRIO 4 Se n é um número inteiro não negativo então binom2nn sumk0n binomnk2 Exercícios 1 Encontre o desenvolvimento de x y4 a usando o raciocínio combinatório como no Exemplo 1 b usando o binômio de Newton 2 Encontre o desenvolvimento de x y5 a usando o raciocínio combinatório como no Exemplo 1 b usando o binômio de Newton cada caminho seja construído a partir de uma série de passos em que cada passo seja um movimento de uma unidade para a direita ou um movimento de uma unidade para cima Movimentos para a esquerda ou para baixo não são permitidos Dois caminhos de 0 0 a 5 3 são ilustrados aqui Utilizados concorrentemente os métodos descritos anteriormente neste capítulo e os métodos introduzidos nesta seção formam uma ferramenta muito útil para a resolução de uma grande variedade de problemas de contagem Quando os métodos adicionais discutidos no Capítulo 7 forem somados a estes você será capaz de resolver inúmeros problemas de contagem que aparecem em muitas áreas de estudo Há quantas maneiras de escolher cinco cédulas possíveis em uma caixa que contém cédulas de RS 1 RS 2 RS 5 RS 10 RS 20 RS 50 e RS 100 Considere que a ordem na qual cada cédula é escolhida não é relevante que cada nota é idêntica e que há pelo menos cinco cédulas de cada valor Há Cn r 1 r Cn r 1 n 1 rcombinações de um conjunto com n elementos quando a repetição dos elementos é permitida do tipo dois e x3 itens do tipo três sejam escolhidos Assim o número de soluções é igual ao número de 11combinações com repetição de um conjunto com três elementos Pelo Teorema 2 verificamos que há C3 11 1 11 C13 2 1312 12 78 soluções O número de soluções desta equação pode também ser encontrado quando as variáveis estão sujeitas à restrição Por exemplo podemos encontrar o número de soluções em que as variáveis são números inteiros com x1 1 x2 2 e x3 3 Uma solução dessa equação sujeita a essas restrições corresponde a uma seleção de 11 itens em que x1 itens do tipo um x2 itens do tipo dois e x3 itens do tipo três em que há pelo menos um item do tipo um dois itens do tipo dois e três do tipo três Depois selecionamos cinco itens adicionais Pelo Teorema 2 isto pode ser feito de 21 maneiras Portanto há 21 soluções possíveis para a equação sujeita às restrições dadas EXEMPLO 6 Qual o valor de k depois que o pseudocódigo abaixo for executado k 0 for i1 1 to n for i2 1 to i1 for ik 1 to im1 k k 1 Solução Note que o valor inicial de k é 0 e que 1 é adicionado a k toda vez que o laço for dado com uma sequência de inteiros i1 i2 im tal que 1 i1 i2 ik n O número de tais sequências é o número de maneiras de escolher m números inteiros de 1 2 n com repetição Para verificar isso note que uma vez que a sequência for escolhida a ordem dos números inteiros forma uma ordem não decrescente esta unicidade define uma tarefa de imim1 Contrariamente cada tarefa corresponde a um único conjunto não ordenado Assim pelo Teorema 2 temos que k Cn m 1 m depois que o código tiver sido executado As fórmulas para os números de seleções ordenadas e não ordenadas de r elementos com sem repetições de um conjunto com c elementos são apresentadas na Tabela 1