Exercícios de Matemática Discreta

Prévia do material em texto

<p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>CET0194 - Matemática Discreta</p><p>Lista 1. Lista de Exerćıcios.</p><p>Exerćıcio 1. Prove, por indução, que (</p><p>n+ 1</p><p>n</p><p>)n</p><p>⩽ n</p><p>para todo n ⩾ 3 e conclua dáı que a sequência</p><p>1,</p><p>√</p><p>2,</p><p>3</p><p>√</p><p>3,</p><p>4</p><p>√</p><p>4 . . .</p><p>é decrescente a partir do terceiro termo.</p><p>Exerćıcio 2. Prove, por indução, que</p><p>1 + 22 + 32 + · · ·+ n2 =</p><p>n(n+ 1)(2n+ 1)</p><p>6</p><p>.</p><p>Exerćıcio 3. Critique a seguinte argumentação: Quer-se provar que todo número natural é</p><p>pequeno. Evidentemente, 1 é um número pequeno. Além disso, se n for pequeno, n+ 1 também</p><p>o será, pois não se torna grande um número pequeno simplesmente somando-lhe uma unidade.</p><p>Logo, por indução, todo número natural é pequeno.</p><p>Exerćıcio 4. Seja P (n) uma propriedade relativa ao número natural n. Suponha que P (1), P (2)</p><p>são verdadeiras e que, para qualquer n ∈ N, a verdade de P (n) e P (n+ 1) implica a verdade de</p><p>P (n+ 2). Prove que P (n) é verdadeira para todo n ∈ N.</p><p>Exerćıcio 5. Use indução para provar que</p><p>13 + 23 + 33 + · · ·+ n3 =</p><p>1</p><p>4</p><p>n2(n+ 1)2.</p><p>Exerćıcio 6. Mostre, por indução, a validez das seguintes fórmulas:</p><p>(a) 1.20 + 2.21 + 3.22 + · · ·+ n.2n−1 = 1 + (n− 1)2n;</p><p>(b)</p><p>(</p><p>1 + 1</p><p>1</p><p>) (</p><p>1 + 1</p><p>2</p><p>)2 · · · (1 + 1</p><p>n−1</p><p>)n−1</p><p>= nn−1</p><p>(n−1)!</p><p>,</p><p>(c) 1.1! + 2.2! + 3.3! + · · ·+ n.n! = (n+ 1)!− 1.</p><p>Exerćıcio 7. Sejam a e b números reais distintos. Mostre que, para todo n ∈ N, vale a igualdade:</p><p>bn + abn−1 + a2bn−2 + · · ·+ an−1b+ an =</p><p>bn+1 − an+1</p><p>b− a</p><p>Exerćıcio 8. Mostre que</p><p>(a) n ! > 2n, se n ≥ 4;</p><p>(b) n ! > 3n, se n ≥ 7;</p><p>(c) n! > 4n, se n ≥ 9.</p><p>Exerćıcio 9. Prove que, para todo n natural, vale a desigualdade:</p><p>1</p><p>2</p><p>· 3</p><p>4</p><p>· 5</p><p>6</p><p>· · · 2n− 1</p><p>2n</p><p>≤ 1√</p><p>3n+ 1</p><p>.</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 1</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>Exerćıcio 10. Mostre que o número de diagonais de um poĺıgono convexo de n lados é dado por</p><p>dn =</p><p>n(n− 3)</p><p>2</p><p>.</p><p>Exerćıcio 11. Prove que:</p><p>(a) 2n > n, onde n é um número natural arbitrário;</p><p>(b) 1·3·5···(2n−1)</p><p>2·4·6···2n ≤ 1√</p><p>2n+1</p><p>, para qualquer n ∈ N;</p><p>(c) 1</p><p>n+1</p><p>+ 1</p><p>n+2</p><p>+ · · ·+ 1</p><p>2n</p><p>> 13</p><p>24</p><p>, se n ∈ N e n ≥ 2;</p><p>(d) 2n > 1 + n</p><p>√</p><p>2n−1, se n ∈ N e n ≥ 2.</p><p>Exerćıcio 12. Suponha que x + 1</p><p>x</p><p>seja um número natural. Prove que xn + 1</p><p>xn é também um</p><p>número natural, qualquer que seja o número natural n.</p><p>Exerćıcio 13. Ache o erro na ”prova”do seguinte</p><p>”Teorema”: Todos os números naturais são iguais.</p><p>Vamos provar o resultado mostrando que, para todo n ∈ N, é verdadeira a sentença</p><p>P (n) : : dado n ∈ N, todos os número naturais menores ou iguais do que n são iguais.</p><p>(i) P (1) é claramente verdadeira.</p><p>(ii) Suponha que P (n) seja verdadeira, logo n − 1 = n. Somando 1 a ambos os lados dessa</p><p>igualdade, obtemos n = n+1. Como n era igual a todos os naturais anteriores, segue que P (n+1)</p><p>é verdadeira.</p><p>Portanto, P (n) é verdadeira para todo n ∈ N .</p><p>Exerćıcio 14. Ache o erro na ”prova”do seguinte</p><p>”Teorema”: Todos os patos de um certo lago são brancos.</p><p>(i) O primeiro pato a ser observado é branco.</p><p>(ii) O pato de número 200 a ser observado é branco, sendo que todos os 199 anteriores também</p><p>eram branco.</p><p>Portanto, todo pato deste lago é branco.</p><p>Exerćıcio 15. Formam-se n triângulos com palitos, conforme as figuras abaixo. Qual o número</p><p>de palitos usados para construir n triângulos?</p><p>n = 1</p><p>n = 2</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 2</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>n = 3</p><p>Exerćıcio 16. Quanto vale o produto (a)(aq) (aq2) (aq3) . . . (aqn−1)?</p><p>Resposta. an · q</p><p>n(n−1)</p><p>2 .</p><p>Exerćıcio 17. Um quadrado mágico de ordem n é uma matriz n × n, cujos elementos são os</p><p>inteiros 1, 2, . . . , n2, sem repetir nenhum, tal que todas as linhas e todas as colunas têm a mesma</p><p>soma. O valor dessa soma é chamado de constante mágica. Por exemplo, os quadrados</p><p> 1 5 9</p><p>8 3 4</p><p>6 7 2</p><p></p><p> 8 1 6</p><p>3 5 7</p><p>4 9 2</p><p> e</p><p></p><p>17 24 1 8 15</p><p>23 5 7 14 16</p><p>4 6 13 20 22</p><p>10 12 19 21 3</p><p>11 18 25 2 9</p><p></p><p>são mágicos, com constantes mágicas respectivamente iguais a 15, 15 e 65. Aliás, os dois últimos</p><p>são hipermágicos, pois as linhas, colunas e também as diagonais têm a mesma soma. Calcule a</p><p>constante mágica de um quadrado mágico de ordem n.</p><p>Exerćıcio 18. Suprimindo um dos elementos do conjunto {1, 2, . . . , n}, a média aritmética dos</p><p>elementos restantes é 16,1 . Determine o valor de n e qual foi o elemento suprimido.</p><p>Exerćıcio 19. Na primeira fase do campeonato brasileiro de futebol, que é disputado por 20</p><p>clubes, quaisquer dois times jogam entre si uma única vez. Quantos jogos há?</p><p>Exerćıcio 20. Qual o número máximo de regiões em que n retas podem dividir o plano?</p><p>Exerćıcio 21. Há dois tipos de anos bissextos: os que são múltiplos de 4 mas não de 100 e os</p><p>que são múltiplos de 400.</p><p>(a) Quantos são os anos bissextos entre 1997 e 2401?</p><p>(b) Se 1◦ de janeiro de 1997 foi quarta-feira, que dia será 1◦ de janeiro de 2500 ?</p><p>(c) Escolhido um ano ao acaso, qual a probabilidade dele ser bissexto?</p><p>Exerćıcio 22. O número triangular Tn é definido como a soma dos n primeiros termos da pro-</p><p>gressão aritmética 1, 2, 3, 4, . . .. O número quadrangular Qn é definido como a soma dos n primei-</p><p>ros termos da progressão aritmética 1, 3, 5, 7, . . . Analogamente são definidos números pentagonais,</p><p>hexagonais, etc.</p><p>A Figura “Números j-gonais” justifica essa denominação. Determine o número j-gonal de</p><p>ordem n.</p><p>Exerćıcio 23. Os ângulos internos de um pentágono convexo estão em progressão aritmética.</p><p>Determine o ângulo mediano.</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 3</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>Figura 1: Números j-gonais</p><p>Exerćıcio 24. Se 3 − x,−x,</p><p>√</p><p>9− x, . . . é uma progressão aritmética, determine x e calcule o</p><p>quinto termo.</p><p>Exerćıcio 25. Calcule a soma dos termos da progressão aritmética 2, 5, 8, 11, . . . desde - 25◦ até</p><p>o 41◦ termo, inclusive.</p><p>Exerćıcio 26. Quantos são os inteiros, compreendidos entre 100 e 500, que não são diviśıveis</p><p>nem por 2 , nem por 3 e nem por 5? Quanto vale a soma desses inteiros?</p><p>Exerćıcio 27. Determine o primeiro termo e a razão da progressão aritmética na qual a soma</p><p>dos n primeiros termos é, para todo n:</p><p>(a) Sn = 2n2 + n</p><p>(b) Sn = n2 + n+ 1</p><p>Exerćıcio 28. Determine no quadro abaixo:</p><p>1</p><p>3 5</p><p>7 9 11</p><p>13 15 17 19</p><p>21 23 25 27 29</p><p>(a) o primeiro elemento da 31a linha.</p><p>(b) a soma dos elementos da 31a linha.</p><p>Exerćıcio 29. Determine três números em progressão geométrica, conhecendo sua soma 19 e a</p><p>soma de seus quadrados 133.</p><p>Exerćıcio 30. Número perfeito é aquele que é igual a metade da soma dos seus divisores positivos.</p><p>Por exemplo, 6 é perfeito pois a soma dos seus divisores é 1+2+ 3+6 = 12. Prove que, se 2p− 1</p><p>é um número primo, então 2p−1. (2p − 1) é um número perfeito.</p><p>Exerćıcio 31. Calcule o valor da soma de n parcelas 1 + 11 + · · ·+ 111 . . . 1.</p><p>Exerćıcio 32. Um garrafão contém p litros de vinho. Retira-se um litro de vinho do garrafão e</p><p>acrescenta-se um litro de água, obtendo-se uma mistura homogênea; retira-se, a seguir um litro</p><p>da mistura e acrescenta-se um litro de água e assim por diante. Qual a quantidade de vinho que</p><p>restará no</p><p>garrafão após n dessas operações?</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 4</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>Exerćıcio 33. Larga-se uma bola de uma altura de 5 cm . Após cada choque com o solo, ela</p><p>recupera apenas 4/9 da altura anterior. Determine:</p><p>a) A distância total percorrida pela bola.</p><p>b) O tempo gasto pela bola até parar.</p><p>Exerćıcio 34. Se (an) é uma progressão geométrica de termos positivos, prove que (bn) definida</p><p>por bn = log an é uma progressão aritmética.</p><p>Exerćıcio 35. Se (an) é uma progressão aritmética, prove que (bn) definida por bn = ean é uma</p><p>progressão geométrica.</p><p>Exerćıcio 36. Seja A =</p><p>[</p><p>1 2</p><p>2 4</p><p>]</p><p>. Determine An.</p><p>Exerćıcio 37. Se a base de um retângulo aumenta de 10% e a altura diminui de 10%, de quanto</p><p>aumenta a área?</p><p>Exerćıcio 38. Os lados de um triângulo retângulo formam uma progressão geométrica crescente.</p><p>Determine a razão dessa progressão.</p><p>Exerćıcio 39. Os lados de um triângulo estão em progressão geométrica. Entre que valores pode</p><p>variar a razão?</p><p>Exerćıcio 40. Qual o quarto termo da progressão geométrica</p><p>√</p><p>2, 3</p><p>√</p><p>2, 6</p><p>√</p><p>2, . . .?</p><p>Exerćıcio 41. A soma de três números em progressão geométrica é 19. Subtraindo-se 1 ao</p><p>primeiro, eles passam a formar um progressão aritmética. Calcule-os.</p><p>Exerćıcio 42. Quatro números são tais que os três primeiros formam uma progressão aritmética</p><p>de razão 6 , os três últimos uma progressão geométrica e o primeiro número é igual ao quarto.</p><p>Determine-os.</p><p>Exerćıcio 43. Sheila e Helena disputam uma série de partidas. Cada partida é iniciada por quem</p><p>venceu a partida anterior. Em cada partida, quem iniciou tem probabilidade 0,6 de ganhá-la e</p><p>probabilidade 0,4 de perdê-la. Se Helena iniciou a primeira partida, qual é a probabilidade de</p><p>Sheila ganhar a n ésima partida?</p><p>Exerćıcio 44. Resolva as seguintes recorrências:</p><p>a) xn+1 = (n+ 1)xn + n, x1 = 1; (Resposta. xn = 2n!− 1)</p><p>b) (n+ 1)xn+1 + nxn = 2n− 3, x1 = 1; (Resposta. xn = 1− 2+(−1)n</p><p>n</p><p>)</p><p>c) xn+1 − nxn = (n+ 1)!, x1 = 1. (Resposta. xn = (n+1)!</p><p>2</p><p>)</p><p>Exerćıcio 45. Resolva as recorrências a seguir:</p><p>a) xn+2 + 5xn+1 + 6xn = 0. (Resposta. xn = C1(−2)n + C2(−3)n)</p><p>b) xn+2 + 6xn+1 + 9xn = 0. (Resposta. xn = C1(−3)n + C2 · n · (−3)n)</p><p>c) xn+2 + 2xn+1 + 2xn = 0. (Resposta. xn =</p><p>√</p><p>2</p><p>n (</p><p>C1 cos</p><p>(</p><p>n3π</p><p>4</p><p>)</p><p>+ C2 sen</p><p>(</p><p>n3π</p><p>4</p><p>))</p><p>)</p><p>d) xn+2 + 5xn+1 + 6xn = 0; x0 = 3; x1 = −6. (Resposta. xn = 3(−2)n)</p><p>Exerćıcio 46. Quantos são os gabaritos posśıveis de um teste de 10 questões de múltipla escolha,</p><p>com 5 alternativas por questão?</p><p>Resposta. 510 = 9.765.625.</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 5</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>Exerćıcio 47. Quantos subconjuntos possui um conjunto que tem n elementos?</p><p>Exerćıcio 48. De quantos modos 5 homens e 5 mulheres podem se sentar em 5 bancos de 2</p><p>lugares, se em cada banco deve haver um homem e uma mulher?</p><p>Resposta. 122 · 25 = 460.800.</p><p>Exerćıcio 49. De quantos modos podemos colocar 2 reis diferentes em casas não adjacentes de</p><p>um tabuleiro 8× 8 ? E se os reis fossem iguais?</p><p>Exerćıcio 50. De quantos modos podemos colocar 8 torres iguais em um tabuleiro 8×8, de modo</p><p>que não haja duas torres na mesma linha ou na mesma coluna? E se as torres fossem diferentes?</p><p>Resposta. Torres iguais: 8! = 40.320. Torres diferentes: (8!)2 = 1.625.702.400.</p><p>Exerćıcio 51. De um baralho comum de 52 cartas, sacam-se sucessivamente e sem reposição</p><p>duas cartas. De quantos modos isso pode ser feito se a primeira carta deve ser de copas e a</p><p>segunda não deve ser um rei?</p><p>Exerćıcio 52. O conjunto A possui 4 elementos e, o conjunto B, 7 elementos. Quantas funções</p><p>f : A → B existem? Quantas delas são injetoras?</p><p>Resposta. Funções: 74 = 2.401. Funções injetoras: 7 · 6 · 5 · 4 = 840.</p><p>Exerćıcio 53. a) De quantos modos o número 720 pode ser decomposto em um produto de dois</p><p>inteiros positivos? Aqui consideramos, naturalmente, 8× 90 como sendo o mesmo que 90× 8.</p><p>b) E o número 144?</p><p>Exerćıcio 54. Quantos são os anagramas da palavra ”CAPITULO”:</p><p>a) posśıveis? (Resposta. 8! = 40.320)</p><p>b) que começam e terminam por vogal? (Resposta. 4 · 3 · 6! = 8.640)</p><p>c) que têm as vogais e as consoantes intercaladas? (Resposta. 576 + 576 = 1.152)</p><p>d) que têm as letras c, a, p juntas nessa ordem? (Resposta. 6! = 720)</p><p>e) que têm as letras c, a, p juntas em qualquer ordem? (Resposta. 3! · 6! = 4.320)</p><p>f) que têm a letra p em primeiro lugar e a letra a em segundo? (Resposta. 6! = 720)</p><p>g) que têm a letra p em primeiro lugar ou a letra a em segundo? (Resposta. 7!+7!−6! = 9.360)</p><p>h) que têm p em primeiro lugar ou a em segundo ou c em terceiro? (Resposta. 3·7!−3·6!+5! =</p><p>13.080)</p><p>i) nos quais a letra a é uma das letras à esquerda de p e a letra c é uma das letras à direita de</p><p>p? (Resposta. 8!/6 = 6.720)</p><p>Exerćıcio 55. Se A é um conjunto de n elementos, quantas são as funções f : A → A bijetoras?</p><p>Exerćıcio 56. De quantos modos é posśıvel colocar 8 pessoas em fila de modo que duas dessas</p><p>pessoas, Vera e Paulo, não fiquem juntas?</p><p>Resposta. 8!− 2 · 7! = 30.240.</p><p>Exerćıcio 57. De quantos modos é posśıvel colocar 8 pessoas em fila de modo que duas dessas</p><p>pessoas, Vera e Paulo, não fiquem juntas e duas outras, Helena e Pedro, permaneçam juntas?</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 6</p><p>Universidade Federal do Oeste da Bahia – UFOB</p><p>Centro das Ciências Exatas e das Tecnologias – CCET</p><p>Cursos de Graduação do CCET</p><p>CET0194 - Matemática Discreta</p><p>Prof. Dr. Vinicius Bittencourt</p><p>vinicius.bittencourt@ufob.edu.br</p><p>Exerćıcio 58. Quantas são as permutações simples dos números</p><p>1, 2, 3, . . . , 10</p><p>nas quais o elemento que ocupa o lugar de ordem k, da esquerda para a direita, é sempre maior</p><p>que k − 3?</p><p>Resposta. 38 · 2 · 1 = 13.122.</p><p>Exerćıcio 59. De quantos modos é posśıvel dividir 15 atletas em três times de 5 atletas?</p><p>Exerćıcio 60. De quantos modos é posśıvel dividir 20 objetos em 4 grupos de 3 ou 2 grupos de</p><p>4?</p><p>Resposta.</p><p>20!</p><p>(3!)4(4!)24!2!</p><p>= 67.897.830.000.</p><p>Exerćıcio 61. Um campeonato é disputados por 12 clubes em rodadas de 6 jogos cada. De</p><p>quantos modos é posśıvel selecionar os jogos da primeira rodada?</p><p>Exerćıcio 62. Permutam-se de todas as formas posśıveis os algarismos 1, 2, 4, 6, 7 e escrevem-se</p><p>os números assim formados em ordem crescente. Determine:</p><p>a) que lugar ocupa 62417. (Resposta. 24 + 24 + 24 + 6 + 2 = 80 antes, portanto ele é o 81º)</p><p>b) que número que ocupa o 66◦ lugar. (Resposta. 46.721)</p><p>c) qual o 166◦ algarismo escrito. (Resposta. 2)</p><p>d) a soma dos números assim formados. (Resposta. 480 + 4.800 + 48.000 + 480.000 +</p><p>4.800.000 = 5.333.280)</p><p>Lista de Exerćıcios | CET0194 - Matemática Discreta | 2024/1 | UFOB 7</p>