Principio da Boa Ordenacao e Torneios Round-Robin - Exemplos e Solucoes

Exemplos Extras Solução Considere S como o conjunto de números inteiros não negativos na forma a dq em que q é um número inteiro Este conjunto não é vazio pois dq pode ser tão grande quanto desejar considerando q como um número inteiro negativo com valor absoluto alto Pela propriedade da boa ordenação S tem um menor elemento r a dq0 O número inteiro r não é negativo É também o caso de que r d Se ele não for então terá um elemento não negativo menor em S ou seja a d q0 1 Para isso suponha que r d Como a dq0 r temos que a d q0 1 a dq0 d r d 0 Conseqüentemente existem números inteiros q e r com 0 r d A demonstração de que q e r são únicos é deixada como exercício para o leitor EXEMPLO 6 Em um torneio Roundrobin cada jogador joga com outro jogador apenas uma vez e cada jogada tem um vencedor e um perdedor Dizemos que os jogadores p1 p2 pm formam um ciclo se p1 bater p2 p2 bater p3 pm1 bater pm e pm bater p1 Use o princípio da boa ordenação para mostrar que se houver um ciclo de extensão m m 3 entre os jogadores em um torneio Roundrobin deverá haver um ciclo de três desses jogadores Solução Assumimos que não haja ciclos de três jogadores Como há pelo menos um ciclo no torneio todos contra todos o conjunto de todos os números inteiros positivos n para o qual existe um ciclo de extensão n não é vazio Pela propriedade da boa ordenação este conjunto de números inteiros positivos tem pelo menos um elemento k que por hipótese deve ser maior que três Conseqüentemente há um ciclo de jogadores p1 p2 p3 pk e não há ciclos menores Como não há ciclos de três jogadores sabemos que k 3 Considere os três primeiros elementos desse ciclo p1 p2 e p3 Há duas possibilidades de jogadas entre p1 e p3 Se p3 bater p1 temos que p1 p2 p3 é um ciclo de extensão três contradizendo nossa hipótese de que não há ciclos de três jogadores Conseqüentemente deverá haver o caso em que p1 bate p3 Isso significa que podemos omitir p2 do ciclo p1 p2 p3 pk para obter o ciclo p1 p3 p4 pk de extensão k 1 contradizendo a hipótese de que o menor ciclo tem extensão k Concluímos que deve haver um ciclo de extensão três Exercícios 1 Use a indução completa para mostrar que se você puder correr um ou dois quilômetros e se uma vez que tenha corrido determinado número de quilômetros puder sempre correr dois quilômetros a mais então você pode correr qualquer número de quilômetros 2 Use a indução completa para mostrar que todos os dominós caem em um arranjo infinito de dominós se soubermos que os três primeiros caem e que quando um dominó cai aquele que fica três posições a frente também cai 3 Considere Pn como a proposição que afirma que uma postagem de n centavos pode ser feita usandose apenas selos de 3 e 5 centavos Os itens deste exercício formam uma demonstração por indução completa de que Pn é verdadeira para n 8 a Mostre que as proposições P8 P9 e P10 são verdadeiras completando o passo base da demonstração b Qual é a hipótese indutiva da demonstração c O que você precisa para demonstrar o passo de indução d Complete o passo de indução para k 10 e Explique por que esses passos mostram que esta proposição é verdadeira sempre que n 8 4 Considere Pn como a proposição que afirma que uma postagem de n centavos pode ser feita usandose apenas selos de 4 e 7 centavos Os itens deste exercício formam uma demonstração por indução completa de que Pn é verdadeira para n 18 a Mostre que as proposições P18 P19 P20 e P21 são verdadeiras completando o passo base da demonstração b Qual é a hipótese indutiva da demonstração c O que você precisa para demonstrar o passo de indução d Complete a etapa indutiva para k 21 e Explique por que esses passos mostram que a proposição é verdadeira sempre que n 18 5 a Determine quais postagens podem ser feitas usandose apenas selos de 4 e 11 centavos 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 c Demonstre sua resposta de a usando a indução completa Em que a hipótese indutiva dessa demonstração difere da demonstração usada com indução matemática 6 a Determine quais postagens podem ser feitas usandose apenas selos de 3 e 10 centavos 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 c Demonstre sua resposta de a usando a indução completa Em que difere a hipótese indutiva dessa demonstração da demonstração usada com indução matemática 7 Qual a quantia de dinheiro que pode ser reunida usando apenas notas de 2 e 5 Demonstre sua resposta usando a indução completa 8 Suponha que uma loja ofereça valespresente nos valores de 25 e 40 Determine quais valores você pode juntar usando estes valespresente Demonstre sua resposta usando a indução completa 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 b 10 Assuma que uma barra de chocolate tenha n quadrados organizados em formato retangular A barra com um pedaço retangular a menos que a barra original pode ser quebrada na horizontal ou na vertical separandose os quadrados Admitindo que apenas um pedaço pode ser quebrado de cada vez quantas vezes você deve quebrar a barra sucessivamente em n quadrados separados Use a indução completa para demonstrar sua resposta 11 Considere esta variação do jogo de Nim O jogo começa com n jogadas Dois jogadores podem remover as cartas uma duas ou três de cada vez O jogador que remover a última carta perde Use a indução completa para mostrar que se cada jogador jogar com a melhor estratégia possível o primeiro vence se n 4j 4j 2 ou 4j 3 para qualquer número inteiro não negativo j e o segundo jogador vence no outro caso possível quando n 4j 1 para qualquer número inteiro não negativo j 12 Use a indução completa para mostrar que todo número inteiro positivo n pode ser escrito como uma soma de potências distintas de dois ou seja como uma soma de um subconjunto de números inteiros 20 1 21 2 22 4 e assim por diante Dica Para o passo de indução considere separadamente o caso em que k 1 é par e em que ele é ímpar Quando for par note que k 12 é um número inteiro 13 Um quebracabeça é montado por junções sucessivas de peças que se organizam em blocos Um movimento é feito cada vez que uma peça é adicionada a um bloco ou quando dois blocos são agrupados Use a indução completa para demonstrar que não importa como os movimentos são realizados são necessários n 1 movimentos para montar um quebracabeça com n peças 14 Suponha que você comece com uma pilha de n pedras e dividaa em n pilhas com uma pedra cada separando sucessivamente uma pilha de pedras em duas menores Cada vez que você faz a divisão multiplica o número de pedras em cada uma das pilhas menores formadas para que elas tenham r e s pedras respectivamente você computa rs Mostre que não importa como você separa as pilhas a soma dos produtos computados em cada etapa é igual a nn 12 15 Prove que o primeiro jogador tem uma estratégia vencedora para o jogo Chomp introduzido no Exemplo 12 da Seção 17 se o quadro inicial for quadrado Dica Use a indução completa para mostrar que esta estratégia funciona Para o primeiro movimento o primeiro jogador mastiga todos os biscoitos exceto aqueles da esquerda e da margem superior Nos movimentos subseqüentes depois que o segundo jogador mastigar os biscoitos do topo ou da extrema esquerda o primeiro jogador mastiga os biscoitos nas mesmas posições relativas da esquerda ou da margem superior respectivamente 16 Demonstre que o primeiro jogador tem uma estratégia para ganhar o jogo Chomp introduzido no Exemplo 12 da Seção 17 se o quadro inicial tiver dois quadrados de largura ou seja um quadro de 2 n Dica Use a indução completa O primeiro movimento do primeiro jogador deve ser mastigar o biscoito na linha inferior da extremidade direita 17 Use a indução completa para mostrar que se um polígono simples com pelo menos quatro lados for triangulado então pelo menos dois desses triângulos da triangulação têm dois lados que delimitam o exterior do polígono 18 Use a indução completa para mostrar que quando um polígono convexo P com vértices consecutivos v1 v2 vn é triangulado em n 2 triângulos os n 2 triângulos podem ser numerados em 1 2 n 2 para que vi seja um vértice do triângulo i para i 1 2 n 2 19 O teorema de Pick diz que a área de um polígono simples P no plano com vértices que são todos pontos reticulados isto é com coordenadas inteiras é igual a IP BP2 1 em que IP e BP são os números de pontos reticulados no interior de P e na borda de P respectivamente Use a indução completa sobre o número de vértices de P para demonstrar o teorema de Pick Dica Para o passo base primeiro demonstre o teorema para retângulos depois para triângulos retos e finalmente para todos os triângulos notando que a área de um triângulo é a área de um retângulo que contém a área de no máximo três triângulos subtraída Para o passo de indução utilize o Lema 1 20 Suponha que P seja um polígono simples com vértices v1 v2 vn listados como vértices consecutivos que estão ligados por um lado e v1 e vn estão ligados por outro lado Um vértice vi é chamado de orelha se o segmento de reta que liga dois vértices adjacentes a vi for uma diagonal interna do polígono simples Duas orelhas vi e vj são chamadas de não sobrepostas se os interiores dos triângulos com vértices vi e seus dois vértices adjacentes e vj e seus dois vértices adjacentes não se cruzarem Demonstre que todo polígono simples com pelo menos quatro vértices tem pelo menos duas orelhas não sobrepostas 21 Na demonstração do Lema 1 mencionamos que muitos métodos incorretos para encontrar um vértice p tal que o segmento de reta bp seja uma diagonal interna de P têm sido publicados Este exercício apresenta algumas maneiras incorretas p que foram escolhidas nessas demonstrações Mostre considerando um dos polígonos desenhados aqui que para cada uma dessas escolhas de p o segmento de reta bp não é necessariamente uma diagonal interna de P a p é o vértice de P tal que o ângulo abp é o menor b p é o vértice de P com a menor coordenada x diferente de b c p é o vértice de P mais próximo de b Os exercícios 22 e 23 apresentam exemplos que mostram como a carga indutiva pode ser utilizada para demonstrar resultados em geometria computacional 22 Considere Pn como a proposição que afirma que quando as diagonais que não se cruzam são desenhadas em um polígono convexo com n lados pelo menos dois vértices do polígono não são pontos finais de qualquer uma dessas diagonais a Mostre que quando tentamos demonstrar Pn para todos os números inteiros n com n 3 usando a indução completa o passo de indução não se sustenta b Mostre que podemos demonstrar que Pn é verdadeira para todos os números inteiros n com n 3 demonstrando pela indução completa a asserção forte Qn para n 4 em que Qn afirma que sempre que diagonais que não se cruzam são desenhadas dentro de um polígono convexo com n lados pelo menos dois vértices não adjacentes não são pontos finais de qualquer uma dessas diagonais 23 Considere En como a proposição que afirma que em uma triangulação de um polígono simples de n lados pelo menos um dos triângulos da triangulação tem dois lados que delimitam o exterior do polígono a Explique onde uma demonstração que usa a indução completa de que En seja verdadeira para todos os números inteiros n 4 é executada com dificuldade b Mostre que podemos demonstrar que En é verdadeira para todos os números inteiros n 4 demonstrando pela indução completa que a proposição forte Tn para todos os números inteiros n 4 que afirma que em toda triangulação de um polígono simples pelo menos dois triângulos da triangulação têm dois lados que delimitam o exterior do polígono 24 Uma tarefa estável definida no preâmbulo do Exercício 58 da Seção 31 é chamada de ideal para os pretendentes se não houver tarefas estáveis nas quais um pretendente é colocado em frente de uma pretendente de sua preferência na tarefa estável Use a indução completa para mostrar que o algoritmo de aceitação produz uma tarefa estável que é ideal para os pretendentes 25 Suponha que Pn seja uma função proposicional Determine se para cada número inteiro positivo n a proposição Pn deve ser verdadeira e justifique sua resposta se a p1 for verdadeira para todos os números inteiros positivos n se Pn for verdadeira então Pn 2 é verdadeira b P1 e P2 forem verdadeiros para todos os números inteiros positivos n se Pn e Pn 1 forem verdadeiras então Pn 2 é verdadeira c P1 for verdadeira para todos os números inteiros positivos n se Pn for verdadeira então P2n é verdadeira d P1 for verdadeira para todos os números inteiros positivos n se Pn for verdadeira então Pn 1 é verdadeira 26 Suponha que Pn seja uma função proposicional Determine se para todo número inteiro não negativo n a proposição Pn deve ser verdadeira se a P0 for verdadeira para todos os números inteiros não negativos n se Pn for verdadeira então Pn 2 é verdadeira b P0 for verdadeira para todos os números inteiros não negativos n se Pn for verdadeira então Pn 3 é verdadeira c P0 e P1 forem verdadeiras para todos os números inteiros não negativos n se Pn e Pn 1 forem verdadeiras então Pn 2 é verdadeira d P0 for verdadeira para todos os números inteiros não negativos n se Pn for verdadeira então Pn 2 e Pn 3 são verdadeiras 27 Mostre que se a proposição Pn for verdadeira para infinitos números inteiros positivos n e Pn 1 Pn for verdadeira para todos os números inteiros positivos n então Pn é verdadeira para todos os números inteiros positivos n 28 Considere b como um número inteiro dado e j como um número inteiro positivo dado Mostre que se Pb Pb 1 Pb j forem verdadeiras e Pb Pb 1 Pk Pk 1 for verdadeira para todo número inteiro positivo k b j então Pn é verdadeira para todos os números inteiros n com n b 29 O que há de errado com esta demonstração por indução completa Teorema Para todo número inteiro não negativo n 5n 0 Passo Base 500 Passo de Indução Suponha que 5j0 para todos os números inteiros não negativos j com 0 j k Escreva k1 ij em que i e j são números naturais menores que k 1 Pela hipótese indutiva 5k 1 5i j 5i 5j 0 0 0 30 Encontre a falha na seguinte demonstração de que an 1 para todos os números inteiros não negativos n sempre que a for um número real diferente de zero Passo Base a0 1 é verdadeira pela definição de a0 Passo de Indução Assuma que aj 1 para todos os números inteiros não negativos j com j k Então note que ak1 ak a ak1 111 1 31 Mostre que a indução completa é um método de demonstração válido indicando que ela se sustenta a partir da propriedade da boa ordenação 32 Encontre a falha na seguinte demonstração de que toda postagem de três centavos ou mais pode ser feita usandose apenas selos de três e quatro centavos Passo Base Podemos fazer postagens de três centavos com apenas um selo de três centavos e podemos fazer postagens de quatro centavos usando apenas um selo de quatro centavos Passo de Indução Assuma que podemos fazer postagens de j centavos para todos os números inteiros não negativos j com j k usando apenas selos de três e quatro centavos Então podemos fazer postagens de k 1 centavos substi 294 4 Indução e Recursão 432 tuindo um selo de três centavos por um selo de quatro centavos ou substituindo dois selos de quatro centavos por três selos de três centavos 33 Mostre que podemos demonstrar que Pn k é verdadeira para todos os pares de números inteiros positivos n e k se mostrarmos que a P1 1 é verdadeira e Pn k Pn 1 k Pn k 1 é verdadeira para todos os números inteiros positivos n e k b P1 k é verdadeira para todos os números inteiros positivos k e Pn k Pn 1 k é verdadeira para todos os números inteiros positivos n e k c Pn 1 é verdadeira para todos os números inteiros positivos n e Pn k Pn k 1 é verdadeira para todos os números inteiros positivos n e k 34 Demonstre que Σnj1 j j 1j 2 j k 1 n n 1n 2 n kk 1 para todos os números inteiros positivos k e n Dica Use a técnica utilizada no Exercício 33 35 Mostre que se a1 a2 an forem n números reais distintos exatamente n 1 multiplicações são utilizadas para computar os produtos desses n números não importando quantos parênteses são inseridos em seus produtos Dica Use a indução completa e considere a última multiplicação 36 A propriedade de boa ordenação pode ser utilizada para mostrar que há um único máximo divisor comum de dois números inteiros positivos Considere a e b como números inteiros positivos e considere S como o conjunto dos números inteiros positivos na forma as bt em que s e t são números inteiros a Mostre que S não é vazio b Use a propriedade de boa ordenação para mostrar que S tem um menor elemento c c Mostre que se d for um divisor comum de a e b então d é um divisor de c d Mostre que c a e c b Dica Primeiro assuma que c a Então a qc r em que 0 r c Mostre que r S contradizendo a escolha por c e Conclua a partir dos itens c e d que o máximo divisor comum de a e b existe Termine a demonstração mostrando que este máximo divisor comum é único 37 Considere a como um número inteiro e d como um número inteiro positivo Mostre que os inteiros q e r com a dq r e 0 r d que foram mostrados como existentes no Exemplo 5 são únicos 38 Use a indução matemática para mostrar que um tabuleiro de damas retangular com um número par de células e dois quadrados faltando um branco e um preto pode ser preenchido por dominós 39 Você pode usar a propriedade da boa ordenação para demonstrar a proposição Todo número inteiro positivo pode ser descrito usando não mais que quinze palavras em inglês Assuma que as palavras venham de determinado dicionário de língua inglesa Dica Suponha que existam números inteiros positivos que não podem ser descritos usando não mais que quinze palavras em inglês Pela boa ordenação o menor número inteiro positivo que não pode ser descrito usando não mais que quinze palavras em inglês deveria então existir 40 Use a propriedade da boa ordenação para mostrar que se x e y forem números reais com x y então existe um número racional r com x r y Dica Use a propriedade de Arquimedes dada no Apêndice 1 para encontrar um número inteiro positivo A com A 1y x Então mostre que existe um número racional r com denominador A entre x e y procurando os números x jA em que j é um número inteiro positivo 41 Mostre que a propriedade da boa ordenação pode ser demonstrada quando o princípio da indução matemática for tido como axioma 42 Mostre que o princípio da indução matemática e a indução completa são equivalentes ou seja cada um pode ser mostrado como válido a partir do outro 43 Mostre que podemos demonstrar a propriedade da boa ordenação quando tomamos o princípio da indução matemática ou o da indução completa como um axioma em vez de tomar a propriedade da boa ordenação como um axioma 43 Definições Recursivas e Indução Estrutural Introdução Às vezes é difícil definir um objeto explicitamente Entretanto pode ser fácil definilo em termos dele próprio Esse processo é chamado de recursão Por exemplo a ilustração mostrada na Figura 1 é produzida recursivamente Primeiro é dada uma ilustração Então é realizado um processo de sobreposições de sucessivas centralizações de fotos menores sobre a ilustração anterior Podemos usar a recursão para definir sequências funções e conjuntos Nas discussões anteriores especificamos os termos de uma sequência que usa uma fórmula explícita Por exemplo a sequência de potências de 2 é dada por an 2n para n 0 1 2 Entretanto esta sequência pode também ser definida dandose o primeiro termo da sequência ou seja a0 1 e uma regra para encontrar um termo a partir do anterior ou seja an1 2an para n 0 1 2 Quando definimos uma sequência recursivamente especificando como os seus termos são