Lista 3 - Métodos de Prova - Matemática Discreta 2016-2

UFMG/ICEx/DCC DCC111 — MaTEMATICA DISCRETA LISTA DE EXERCICIOS 3 METODOS DE PROVA CIENCIAS EXATAS & ENGENHARIAS 2° SEMESTRE DE 2016 1. Identifique o erro na prova do teorema abaixo. Teorema: Para todos inteiros k, se k > 0 entao k? + 2k +1 @ um ntimero composto. Prova: Suponha que k é um nimero inteiro tal que k > 0. Se k?+2k+1 é composto, entao k?+2k+1=r-s, para inteiros re s tal que 1 <r < (k?+2k+1)e1l<s < (k?+2k4+1). Ja que k?+2k+1l=r-se ambos r e s estao necessariamente entre 1 e k? +2k+1, entdo k? +2k+1 nao é primo. Assim, k? +2k+1 é composto, o que devia ser mostrado. 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 sao dois inteiros pares quaisquer. Pela definigao de par m = 2k para algum inteiro k e n = 2k para algum inteiro k. Por substituigao, m+n = 2k + 2k = 4k, o que devia ser provado. 3. Identifique o erro na prova do teorema abaixo. Teorema: Seja n um nimero inteiro impar. Sabe-se que |n/2| = (n — 1)/2. Prova: Suponha que n é um ntmero inteiro fmpar. Sabe-se que n = 2k + 1 para algum inteiro k. Conse- quentemente, 2k+1| (2k+1)—-1_ 2k _f 2 — 2 QO Como n = 2k + 1, temos que k = (n — 1)/2. Assim, por substituigaéo temos que |n/2| = (n — 1)/2. Esta prova incorreta usa a questao a ser provada. A igualdade |} | é 0 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 conclusao a ser provada. 4. Prove se a seguinte afirmacao é verdadeira ou nao. Para todos inteiros n, 4(n? +n+1)—3n? é um quadrado perfeito. 5. Prove se a seguinte afirmacao é verdadeira ou nao. Existe um inteiro k tal que k > 4 e 2k? —5k +2 6 primo. 6. Prove se a seguinte afirmacao é verdadeira ou nao. Para todos inteiros n e m, se n—m € par entao n° — m° é par. 7. Prove se a seguinte afirmacao é verdadeira ou nao. O quociente de dois nimeros racionais € um ntimero racional. 8. Prove se a seguinte afirmacao é verdadeira ou nao sem usar manipulacao algébrica, ou seja, sem “resolver” a equacéo. Suponha que m seja um nimero inteiro. Prove se 17|m na equacao: 8-7-6:5-4-3-2-m=17-16-15-14-13-12-11- 10 9. Prove se a seguinte afirmagao é verdadeira ou nao: VY inteiros a,b ec, se alb e alc entao al(b +c) 10. Suponha que vocé esta participando de uma promocao de uma loja que dé um cartao com ntimeros quando um cliente faz uma compra. Se existem ntimeros nesse cartao que somam 100, entao o cliente ganha um prémio de R$100,00. Um cliente recebe um cartéo com os nimeros 1 72 21 15 36 69 81 9 27 42 63 Sem fazer combinações de somas, mostre se o cliente irá ganhar o prêmio ou nã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. 12. Prove que para qualquer inteiro ímpar n, ⌊ n2 4 ⌋ = ( n−1 2 )( n+1 2 ). 13. O resultado de 1 0 é um número irracional? Explique. 14. Prove por contradição que para todos os números primos a, b e c, a2 + b2 ̸= c2. 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. 16. Apresente um teorema cuja prova seja na forma geométrica. 17. Prove que se x2 + y = 13 e y ̸= 4, em que x, y ∈ R, então x ̸= 3. 18. Prove que se x > 0 e x < y, em que x, y ∈ R, então x2 < y2. 19. Prove que min(x, y) + max(x, y) = x + y para quaisquer números reais x e y. 20. Prove por contradição que há uma infinidade de números primos. 21. Prove que se n = ab, sendo a, b ∈ Z+, então a ≤ √n ou b ≤ √n. Prove ou apresente um contra-exemplo para a seguinte afirmação: O produto de quaisquer três números inteiros consecutivos é par. 2