Matemática Discreta - Soluções Lista de Exercícios 3 - Métodos de Prova UFMG

UFMGICExDCC DCC111 MATEMÁTICA DISCRETA LISTA DE EXERCÍCIOS 3 SOLUÇÕES MÉTODOS DE PROVA CIÊNCIAS EXATAS ENGENHARIAS 2º SEMESTRE DE 2014 1 Identifique o erro na prova do teorema abaixo Teorema Para todos inteiros k se k 0 então k² 2k 1 é um número composto Prova Suponha que k é um número inteiro tal que k 0 Se k² 2k 1 é composto então k² 2k 1 r s para inteiros r e s tal que 1 r k² 2k 1 e 1 s k² 2k 1 Já que k² 2k 1 r s e ambos r e s estão necessariamente entre 1 e k² 2k 1 então k² 2k 1 não é primo Assim k² 2k 1 é composto o que devia ser mostrado Resposta A partir do ponto Já que k² 2k 1 r s e ambos r e s estão necessariamente entre 1 e k² 2k 1 então k² 2k 1 não é primo Assim k² 2k 1 é composto o que devia ser mostrado é usada a questão a ser provada Nesse ponto na prova não foi mostrado ainda que k² 2k 1 é um número composto o que devia ser provado 2 Identifique o erro na prova do teorema abaixo Teorema A soma de quaisquer dois inteiros pares é igual a 4k para algum inteiro k Prova Suponha que m e n são dois inteiros pares quaisquer Pela definição de par m 2k para algum inteiro k e n 2k para algum inteiro k Por substituição m n 2k 2k 4k o que devia ser provado Resposta O erro na prova é que o mesmo símbolo k é usado para representar dois números diferentes Ao supor que m e n são iguais a 2k temos que m n e assim a prova é válida apenas para o caso onde m n Se m n a conclusão é em geral falsa Por exemplo 6 4 10 mas 10 4k para qualquer inteiro k 3 Identifique o erro na prova do teorema abaixo Teorema Seja n um número inteiro ímpar Sabese que n2 n 12 Prova Suponha que n é um número inteiro ímpar Sabese que n 2k 1 para algum inteiro k Consequentemente 2k 12 2k 1 12 2k2 k Como n 2k 1 temos que k n 12 Assim por substituição temos que n2 n 12 Esta prova incorreta usa a questão a ser provada A igualdade n2 é o que deve ser provado Ao substituir 2k 1 por n nos dois lados da igualdade e assumindo que o resultado é verdadeiro a prova assume a verdade da conclusão a ser provada Resposta Prova correta Suponha que n é um número inteiro ímpar Sabese que n 2k 1 para algum inteiro k Consequentemente 2k 12 k 12 k Note que k 12 k pela definição da função chão já que k é o maior inteiro menor ou igual a k 12 Ao substituirmos n por 2k 1 no lado direito da equação proposta temos 2k 1 12 2k2 k Assim os lados esquerdo e direito da equação a ser provada são idênticos 11 Prove se a seguinte afirmação é verdadeira ou não A soma de quatro números inteiros consecutivos não é divisível por 4 Resposta Reescrevendo a afirmação números inteiros n n 1 n 2 e n 3 4 n n 1 n 2 n 3 Prova Sejam n n 1 n 2 e n 3 quatro números inteiros consecutivos Essa soma S vale 4n 6 4n 4 2 4n 1 2 que pode ser representada como S 4t 2 Quando S é dividido por 4 temos 2 como resto Assim essa soma não é divisível por 4 12 Prove que para qualquer inteiro ímpar n n²4 n12n12 Resposta Prova Seja n um inteiro ímpar qualquer Pela definição de ímpar n 2k 1 para algum inteiro k Assim temos que n²4 2k 1²4 4k² 4k 14 k² k 14 k² k Note que k² k 14 k² k pela definição da função chão já que k² k é o maior inteiro menor ou igual a k² k 14 Ao substituirmos n por 2k 1 no lado direito da equação proposta temos n 12 n 12 2k 1 12 2k 1 12 2k2 2k 22 k k 1 k² k Assim os lados esquerdo e direito da equação a ser provada são idênticos 13 O resultado de 10 é um número irracional Explique Resposta Sabese que um número irracional é um número real que não é um número racional Assim o resultado de 10 não é um número irracional já que não é um número real divisão por zero não está definida para o conjunto dos números reais 14 Prove por contradição que para todos os números primos a b e c a² b² c² Resposta Prova Suponha que não ou seja suponha que existam números primos a b e c tais que a² b² c² Temos que a² c² b² c bc b Sabemos que c b 1 ou c b 1 já que c b 0 e a² 0 ie c b deve ser positivo Assim temos dois casos Caso 1 c b 1 Os únicos valores possíveis para b e c são c 3 e b 2 para a diferença entre esses números primos ser 1 o que implica que b 2 Logo a² c² b² 3 23 2 5 ie a 5 Mas isto contradiz a suposição que a seja um número primo Caso 2 c b 1 Devemos ter que ambos c b 1 e c b 1 Como a é primo os únicos fatores positivos de a² são 1 a e a² Como ambos c b e c b são maiores que 1 a única possibilidade é que ambos sejam iguais a a Mas isto implica que c b c b ie b b e assim b 0 Isto contradiz a suposição que b seja um número primo Nos dois casos a contradição é falsa e assim a suposição é falsa e a afirmação original é verdadeira 15 Prove por contraposição que se a soma de dois números reais é menor que 50 então pelo menos um dos números é menor que 25 Resposta Reescrevendo formalmente temos x y ℝ se x y 50 então x 25 ou y 25 A forma contrapositive dessa afirmação é x y ℝ se x 25 e y 25 então x y 50 Prova Suponha que x e y sejam números reais específicos mas escolhidos arbitrariamente tais que x 25 e y 25 Consequentemente a b 25 25 50 Assim se x y 50 então x 25 ou y 25 4 Prove se a seguinte afirmação é verdadeira ou não Para todos inteiros n 4n2 n13n2 é um quadrado perfeito Resposta Prova Suponha que n seja um número inteiro Então 4n2 n 1 3n2 4n2 4n 4 3n2 n2 4n 4 n 22 que é um quadrado perfeito já que n 2 é um inteiro 5 Prove se a seguinte afirmação é verdadeira ou não Existe um inteiro k tal que k 4 e 2k2 5k 2 é primo Resposta Para provar que a afirmação é falsa devemos mostrar que a negação é verdadeira A negação é para todos inteiros k para k 4 2k2 5k 2 não é primo Prova da negação Suponha que k seja um inteiro tal que k 4 Devemos mostrar que 2k2 5k 2 não é primo Ao fatorarmos 2k2 5k 2 obtemos 2k 1k 2 Como k 4 podemos fazer as seguintes afirmações sobre cada termo i o termo 2k 1 7 já que 2k 1 2 4 1 7 e ii o termo k 2 2 já que 2k 2 2 4 2 2 Assim cada fator desse número é um inteiro positivo maior ou igual a dois e assim 2k2 5k 2 não é primo 6 Prove se a seguinte afirmação é verdadeira ou não Para todos inteiros n e m se n m é par então n3 m3 é par Resposta Prova Suponha que m e n são quaisquer inteiros tais que m n é par Devemos mostrar que n3 m3 é par Note que n3 m3 n mn2 nm m Sabemos que n m é par pela suposição Temos que n2 nm m é um número inteiro já que potenciação multiplicação e soma são operações fechadas no conjunto dos números inteiros Assim n mn2 nm m é o produto de um número par por um inteiro A multiplicação de um inteiro por um número par pode ser representada pela soma desse inteiro uma quantidade par de vezes o que resulta em um número par Isso é o que devia ser provado 7 Prove se a seguinte afirmação é verdadeira ou não O quociente de dois números racionais é um número racional Resposta Reescrevendo a afirmação números racionais r e s r s é um número racional Prova Seja r um número racional qualquer e s 0 que é um número racional O quociente de r por s é indefinido e assim não é necessariamente um número racional Assim a afirmação é falsa 8 Prove se a seguinte afirmação é verdadeira ou não sem usar manipulação algébrica ou seja sem resolver a equação Suponha que m seja um número inteiro Prove se 17m na equação 8 7 6 5 4 3 2 m 17 16 15 14 13 12 11 10 Resposta Prova O número 17 é um fator primo do número do lado direito da equação e é um fator primo do número do lado esquerdo pelo Teorema Único da Fatorização Mas 17 não é um fator primo de 8 7 6 5 4 3 e 2 Assim 17 deve ocorrer como um fator primo de m e 17m 9 Prove se a seguinte afirmação é verdadeira ou não inteiros a b e c se ab e ac então ab c Resposta Prova Suponha que a b e c são inteiros tal que ab e ac Pela definição de divisibilidade b ar e c as para inteiros r e s Então b c a r a s ar s Logo ab c aar s 10 Suponha que você está participando de uma promoção de uma loja que dá um cartão com números quando um cliente faz uma compra Se existem números nesse cartão que somam 100 então o cliente ganha um prêmio de R10000 Um cliente recebe um cartão com os números 72 21 15 36 69 81 9 27 42 63 2 Sem fazer combinações de somas mostre se o cliente irá ganhar o prêmio ou não Resposta Cada um dos números anteriores é divisível por 3 Qualquer soma com esses números provê como resultado um número que é divisível por 3 Como 100 não é divisível por 3 qualquer soma não será igual a 100 Assim o cliente não ganhará o prêmio com esse cartão 11 Prove se a seguinte afirmação é verdadeira ou não A soma de quatro números inteiros consecutivos não é divisível por 4 Resposta Reescrevendo a afirmação números inteiros n n 1 n 2 e n 3 4 n n 1 n 2 n 3 Prova Sejam n n 1 n 2 e n 3 quatro números inteiros consecutivos Essa soma S vale 4n 6 4n 4 2 4n 1 2 que pode ser representada como S 4t 2 Quando S é dividido por 4 temos 2 como resto Assim essa soma não é divisível por 4 12 Prove que para qualquer inteiro ímpar n n²4 n12n12 Resposta Prova Seja n um inteiro ímpar qualquer Pela definição de ímpar n 2k 1 para algum inteiro k Assim temos que n²4 2k 1²4 4k² 4k 14 k² k 14 k² k Note que k² k 14 k² k pela definição da função chão já que k² k é o maior inteiro menor ou igual a k² k 14 Ao substituirmos n por 2k 1 no lado direito da equação proposta temos n 12 n 12 2k 1 12 2k 1 12 2k2 2k 22 k k 1 k² k Assim os lados esquerdo e direito da equação a ser provada são idênticos 13 O resultado de 10 é um número irracional Explique Resposta Sabese que um número irracional é um número real que não é um número racional Assim o resultado de 10 não é um número irracional já que não é um número real divisão por zero não está definida para o conjunto dos números reais 14 Prove por contradição que para todos os números primos a b e c a² b² c² Resposta Prova Suponha que não ou seja suponha que existam números primos a b e c tais que a² b² c² Temos que a² c² b² c bc b Sabemos que c b 1 ou c b 1 já que c b 0 e a² 0 ie c b deve ser positivo Assim temos dois casos Caso 1 c b 1 Os únicos valores possíveis para b e c são c 3 e b 2 para a diferença entre esses números primos ser 1 o que implica que b 2 Logo a² c² b² 3 23 2 5 ie a 5 Mas isto contradiz a suposição que a seja um número primo Caso 2 c b 1 Devemos ter que ambos c b 1 e c b 1 Como a é primo os únicos fatores positivos de a² são 1 a e a² Como ambos c b e c b são maiores que 1 a única possibilidade é que ambos sejam iguais a a Mas isto implica que c b c b ie b b e assim b 0 Isto contradiz a suposição que b seja um número primo Nos dois casos a contradição é falsa e assim a suposição é falsa e a afirmação original é verdadeira 15 Prove por contraposição que se a soma de dois números reais é menor que 50 então pelo menos um dos números é menor que 25 Resposta Reescrevendo formalmente temos x y ℝ se x y 50 então x 25 ou y 25 A forma contrapositive dessa afirmação é x y ℝ se x 25 e y 25 então x y 50 Prova Suponha que x e y sejam números reais específicos mas escolhidos arbitrariamente tais que x 25 e y 25 Consequentemente a b 25 25 50 Assim se x y 50 então x 25 ou y 25 16 Apresente um teorema cuja prova seja na forma geométrica Resposta Veja a prova para o Teorema de Pitágoras 17 Prove que se x2 y 13 e y 4 em que x y R então x 3 Resposta Prova Sejam x e y números reais arbitrários Suponha o contrário isto é x 3 Substituindose x por 3 em x2 y 13 obtémse 32 y 13 Assim y 13 9 4 o que resulta em uma contradição Portanto se x2 y 13 e y 4 então x 3 18 Prove que se x 0 e x y em que x y R então x2 y2 Resposta Prova Sejam x e y números reais arbitrários tais que x 0 e x y Ou seja temos que 0 x y e portanto y 0 Consequentemente x2 xy y2 De onde se conclui que x2 y2 19 Prove que minx y maxx y x y para quaisquer números reais x e y Resposta Prova Sejam x e y números reais arbitrários Sabese que x y x y ou x y Serão considerados cada um dos três casos x y temse que minx y x e maxx y y x y minx y maxx y x y x y minx y y e maxx y x Em qualquer um dos três casos minx y maxx y x y Portanto minx y maxx y x y para quaisquer números reais x e y 20 Prove por contradição que há uma infinidade de números primos Resposta Prova Suponha que há uma quantidade limitada de números primos p1 p2 pn para algum natural n Seja k p1p2 pn 1 Deste modo k não é divisível por nenhum dos números primosp1 p2 pn Portanto k é divisível por algum outro número primo diferente de p1 p2 pn ou k é primo Em qualquer dos dois casos temse a existência de um primo diferente de p1 p2 pn Isto contradiz a suposição de que existe uma quantidade limitada de números primos 21 Prove que se n ab sendo a b Z então a n ou b n Resposta Prova Sejam a e b dois inteiros positivos tais que a n e b n Multiplicandose as duas desigualdades obtémse ab nn o que implica em ab n Isso mostra que ab n Portanto a proposição é verdadeira 4