Lista 5 - Matemática Discreta 2021-2

UFLA — ICET Departamento de Matematica e Matematica Aplicada Prof. Jamil Abreu t, [ma a: [el UFLA/ICET/DMM eae Sala 10 eee Telefone: +55-35-3821-1643 ‘oe E-mail: jamil.abreuQufla.br 4? e e Matematica Discreta (2021/2) . O ~— Lista n°05 — Ex. 1. Mostre, usando o principio da boa-ordem, que n? + n+ 1 é um numero par para todo natural n. (Dica. Suponha que a afirmacao seja falsa e seja A 0 conjunto dos nimeros naturais n tais que n?+n-+1 é impar; pelo princfpio da boa-ordem, A tem um menor elemento m, logo m? +m-+1 éimpar mas (m — 1)? +(m—1)+4+1 6 par...) A Ex. 2. Complete a demonstracao do principio da boa-ordem: seja A um subconjunto nao-vazio de N; seja B= {n €N: n<k para todo k € A}; sejan € B tal quen+1 ¢ B; mostre que n+1 €0 menor elemento de A. A Ex. 3. Demonstre o principio da indugaéo usando o principio da boa ordem. (Dica. Seja A C N tal quel € Aen+1¢€A sempre quen€ A. SSCAFN, sejaB={meEN:m ¢ A}. Pelo principio da boa-ordem, B tem um menor elemento... ) A Ex. 4 (Opcional). O objetivo deste exercicio é ilustrar uma outra aplicagao da propriedade de que nao hé nimeros naturais entre 0 e 1, desta vez com uma demonstracao da irracionalidade do numero 7. (a) Defina as fungoes polinomiais x*(m — nx) f(z) = a e F(a) = f(a) — f(a) + fO (x) — +--+ (-1)P FP? (2). Note que k! f(x) é uma soma de mondmios com coeficientes inteiros e graus > k, logo f(x) e todas as suas derivadas f(x) nao ntimeros inteiros quando x = 0. (b) Como f(x) = f(m/n — x), a conclusao de (a) é valida também quando x = m/n. (c) Mostre que d Gh) sen az — F(x) cosa] = f(x) senz, x e deduza que | f(a) sena dx = F(m) + F(0). 0 1 (d) Agora, suponha que π seja um n´umero racional, digamos π = m/n, e considere a cons- tru¸c˜ao nos itens (a) e (b) com estes inteiros m e n; explique por que F(π)+F(0) ´e tamb´em um n´umero inteiro. (e) Mostre que se 0 < x < π ent˜ao 0 < f(x) sen x < πkmk k! . Mostre que isto acarreta numa contradi¸c˜ao. ▲ Ex. 5. Vocˆe tem dez pares de cal¸cados, entre tˆenis, sapatos e sand´alias, todos misturados no fundo do guarda-roupas. Quantos cal¸cados, na pior das hip´oteses, vocˆe deve retirar de uma vez para conseguir um par completo? ▲ Ex. 6. Num torneio, n jogadores jogam entre si, cada jogador jogando uma vez com cada um dos demais. Mostre que ao menos dois jogadores ter˜ao o mesmo n´umero de vit´orias. ▲ 2