Lista 3 - 2023-1

Matemática Discreta – Lista 03 Aluno: RGA: 1. Para os exercícios a seguir, escreva os cinco primeiros valores da sequência. a. 𝑆(1) = 10 𝑆(𝑛) = 𝑆(𝑛 – 1) + 10 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 b. 𝐶(1) = 5 𝐶(𝑛) = 2𝐶(𝑛 – 1) + 5 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 c. 𝐵(1) = 1 𝐵(𝑛) = 𝐵(𝑛 – 1) + 𝑛 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 d. 𝑇(1) = 1 𝑇(𝑛) = 𝑛𝑇(𝑛 – 1) 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 e. 𝑃(1) = 1 𝑃(𝑛) = 𝑛2𝑃(𝑛 – 1) + (𝑛 – 1) 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 2. O problema original apresentado por Fibonacci tratava de pares de coelhos. Dois coelhos não cruzam até terem 2 meses de idade. Depois disso, cada par de coelho gera um novo par cada mês. Suponha que nenhum coelho morre. Denote por C(n) o número de pares de coelhos que você terá ao final de n meses se começar com um único par de coelhos. Mostre que C(n) é a sequência de Fibonacci. Em seguida, escreva 27 e 62 como soma de números de Fibonacci distintos não consecutivos. 3. Em um experimento, determinada colônia de bactérias tem uma população inicial de 50.000. A população é contada a cada 2 horas, e, ao final de cada intervalo de 2 horas, a população triplica. Escreva uma definição recorrente para a sequência A(n), o número de bactérias presentes no início do n-ésimo período. No início de que intervalo haverá 1.350.000 bactérias presentes? 4. a) Dê uma definição recorrente para o conjunto de todas as cadeias binárias que são palíndromos (são iguais se lidas normalmente ou de trás para frentes). b) Seja x uma cadeia de determinado alfabeto. De uma definição recorrente para a operação xn (concatenação de x consigo mesmo n vezes) para n ≥ 1. c) Dê uma definição recorrente para o conjunto de todos os inteiros ímpares. d) Dê uma definição recorrente para o conjunto de todas as cadeias binárias que terminam com 0. 5. Nos exercícios a seguir, escreva o corpo de uma função recorrente para calcular S(n), em que S é a sequência dada. a) 1, 3, 9, 27, 81, … b) 2, 1, 1/2, 1/4, 1/8, … c) 1, 2, 4, 7, 11, 16, 22, … d) 2, 4, 16, 256, … 6. Nos exercícios a seguir, resolva a relação de recorrência sujeita à condição básica. a) 𝑆(1) = 5 𝑆(𝑛) = 𝑆(𝑛 – 1) + 5 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 b) 𝐵(1) = 5 𝐵(𝑛) = 3𝐵(𝑛 – 1) 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 c) 𝐹(1) = 2 𝐹(𝑛) = 2𝐹(𝑛 – 1) + 2𝑛 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 d) 𝑇(1) = 1 𝑇(𝑛) = 2𝑇(𝑛 – 1) + 1 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 e) 𝐴(1) = 1 𝐴(𝑛) = 𝐴(𝑛 – 1) + 𝑛 𝑝𝑎𝑟𝑎 𝑛 ≥ 2 7. Uma mensagem contendo um vírus foi enviada a 1000 endereços de correio eletrônico. Depois de 1 segundo uma máquina recipiente transmite 10 novas mensagens com vírus e depois disso o vírus desabilita a si mesmo naquela máquina. a) Escreva uma relação de recorrência para o número de mensagens com vírus enviadas no n-ésimo segundo e a resolva. b) Quantas mensagens com vírus são enviadas no final de 20 segundos, ou seja, no início do 21° segundo? 8. Nas questões a seguir também analise as figuras para uma melhor compreensão: a) Os primeiros membros da Associação de Pitágoras definiram números poligonais como o número de pontos em determinadas configurações geométricas. Os primeiros números triangulares são 1, 3, 6 e 10. Encontre e resolva uma relação de recorrência para o n-ésimo número triangular. b) Os primeiros números pentagonais são 1, 5, 12 e 22. Encontre e resolva uma relação de recorrência para o n-ésimo número pentagonal. 9. Nos exercícios a seguir, resolva a relação de recorrência sujeita às condições iniciais dadas. a) 𝑇(1) = 5 𝑇(2) = 11 𝑇(𝑛) = 5𝑇(𝑛 – 1) – 6𝑇(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 b) 𝐴(1) = 7 𝐴(2) = 18 𝐴(𝑛) = 6𝐴(𝑛 – 1) – 8𝐴(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 c) 𝑆(1) = 4 𝑆(2) = – 2 𝑆(𝑛) = – 𝑆(𝑛 – 1) + 2𝑆(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 d) 𝑃(1) = 5 𝑃(2) = 17 𝑃(𝑛) = 7𝑃(𝑛 – 1) – 12𝑃(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 e) 𝐹(1) = 8 𝐹(2) = 16 𝐹(𝑛) = 6𝐹(𝑛 – 1) – 5𝐹(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 f) 𝑇(1) = – 1 𝑇(2) = 7 𝑇(𝑛) = – 4𝑇(𝑛 – 1) – 3𝑇(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 g) 𝐵(1) = 3 𝐵(2) = 14 𝐵(𝑛) = 4𝐵(𝑛 – 1) – 4𝐵(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 h) 𝐹(1) = – 10 𝐹(2) = 40 𝐹(𝑛) = – 10𝐹(𝑛 – 1) – 25𝐹(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 i) 𝐴(1) = 8 𝐴(2) = 8 𝐴(𝑛) = 2𝐴(𝑛 – 1) – 2𝐴(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 j) 𝑆(1) = 4 𝑆(2) = – 8 𝑆(𝑛) = – 4𝑆(𝑛 – 1) – 5𝑆(𝑛 – 2) 𝑝𝑎𝑟𝑎 𝑛 ≥ 3 10. Um vírus de computador que se prolifera por mensagens de correio eletrônico (e-mail) é colocado em 3 máquinas no primeiro dia. Diariamente, cada computador infectado no dia anterior infecta 5 novas máquinas. No final do segundo dia, é desenvolvido um programa para atacar o vírus, e se limpa 1 computador. Cada dia a partir daí, são limpas 6 vezes mais máquinas do que foram limpas no dia anterior. a) Escreva uma relação de recorrência para o número total de máquinas infectadas num determinado dia n e resolva essa relação. b) Quantos dias irão se passar até os efeitos do vírus estarem completamente eliminados? Matem´atica Discreta 1. Quest˜ao 1 (a) S(1) = 10, S(2) = S(1) + 10 = 20, S(3) = S(2) + 10 = 30, S(4) = S(3) + 10 = 40, S(5) = S(4) + 10 = 50. (b) C(1) = 5, C(2) = 2C(1) + 5 = 15, C(3) = 2C(2) + 5 = 35, C(4) = 2C(3) + 5 = 75, C(5) = 2C(4) + 5 = 155. (c) B(1) = 1, B(2) = B(1) + 2 = 3, B(3) = B(2) + 3 = 6, B(4) = B(3) + 4 = 10, B(5) = B(4) + 5 = 15. (d) T(1) = 1, T(2) = 2T(1) = 2, T(3) = 3T(2) = 6, T(4) = 4T(3) = 24, T(5) = 5T(4) = 120. (e) P(1) = 1, P(2) = 22P(1) + 1 = 5, P(3) = 32P(2) + 2 = 47, P(4) = 42P(3) + 3 = 755, P(5) = 52P(4) + 4 = 18879. 2. Quest˜ao 2 Sabemos que a sequˆencia de Fibonacci tem a seguinte lei de formac¸ ˜ao: F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2), n ≥ 3. Para o problema dos coelhos, C(n) representa a quantidade de pares de coelhos que teremos ao final de n meses, comec¸ando com um ´unico par. Temos ent˜ao C(1) = 1, pois ´e a quantidade de pares inicial, C(2) = 1 tamb´em, pois ao final do segundo mˆes ´e que nosso par inicial estar´a apto a cruzar. C(3) = 2, pois como o par inicial estava apto a cruzar, gerou um novo par, C(4) = 3, pois dos dois pares que t´ınhamos, apenas um estar´a apto a cruzar e para cada novo mˆes, os pares de coelhos aptos a cruzar s˜ao os que existiam h´a 2 meses atr´as, ou seja, C(n − 2), como cada par de C(n + 2) gera um novo par, teremos a quantidade do mˆes anterior C(n − 1) somada aos novos pares que s˜ao na mesma quantidade de C(n − 2), ou seja, C(n) = C(n − 1) + C(n − 2) para n ≥ 3, que ´e exatamente a sequˆencia de Fibonacci. Para escrever os dois n´umeros pedidos, vamos primeiro escrever alguns n´umeros da sequˆencia de Fibonacci: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .} • O n´umero da sequˆencia mais pr´oximo de 27 (sem ultrapass´a-lo) ´e 21, 27 = 21 + 6, como 6 n˜ao est´a na sequˆencia, devemos abr´ı-lo em outra soma. O n´umero mais pr´oximo de 6 na sequˆencia ´e 5 e 6 = 5 + 1. Portanto 27 = 1 + 5 + 21. • O n´umero de Fibonacci mais pr´oximo de 62 ´e o 55 e 62 − 55 = 7, 7 n˜ao ´e um n´umero de Fibonacci, mas 7 = 5 + 2 e 5, 2 s˜ao n´umeros de Fibonacci. Portanto 62 = 55 + 5 + 2. 1 Matem´atica Discreta 3. Quest˜ao 3 Como queremos as bact´erias presentes no in´ıcio do per´ıodo de tempo, ent˜ao a quantidade inicial ´e A(1) = 50000. Como a cada per´ıodo de tempo de duas horas a populac¸ ˜ao triplica, podemos definir de forma recorrente A(n) = 3A(n − 1), A(1) = 50000. Vamos Observar que A(2) = 3A(1), A(3) = 3A(2) = 3·3A(1) = 32A(1), A(4) = 3A(3) = 3·32A(1) = 33A(1), e resolvendo a recorrˆencia encontramos A(n) = 3n−150000. Basta ent˜ao calcular para qual valor de n temos A(n) = 1350000. 3n−150000 = 1350000 =⇒ 3n−1 = 1350000 50000 = 27 =⇒ 3n−1 = 33 =⇒ n = 4 Portanto haver´a 1.350.000 bact´erias no in´ıcio do 4º intervalo de 2 horas. 4. Quest˜ao 4 (a) • A cadeia vazia (ε) ´e um pal´ındromo. • Qualquer cadeia de um ´unico caractere (0 ou 1) ´e um pal´ındromo. • Se uma cadeia comec¸ar e terminar com o mesmo caractere, ela ´e um pal´ındromo se e somente se a subcadeia que exclui esses caracteres iniciais e finais tamb´em for um pal´ındromo. (b) xn = xn−1&x, x1 = x. (c) Fazendo Z(1) = 1 ´e um inteiro ´ımpar. Os inteiros da forma Z(1) + 2 ser˜ao ´ımpares, ent˜ao Z(n) = Z(n − 1) + 2, Z(1) = 1. (d) • ”0”´e uma cadeia bin´aria que termina com 0. • Se ”w”´e uma cadeia bin´aria que termina com 0, ent˜ao ”w0”tamb´em ´e uma cadeia bin´aria que termina com 0. 5. Quest˜ao 5 (a) S(n) = 3S(n − 1), S(1) = 1. (b) S(n) = S(n − 1 2 , S(1) = 2. (c) S(n) = S(n − 1) + (n − 1), S(1) = 1. (d) S(n) = S(n − 1)2, S(1) = 2. 2 Matem´atica Discreta 6. Quest˜ao 6 (a) S(1) = 5 S(2) = S(1) +5 S(3) = S(2) +5 ... ... ... S(n) = S(n − 1) +5 Somando obtemos S(n) = S(1)+5+5+. . .+5 = S(1)+5(n−1). Usando a condic¸ ˜ao b´asica temos: S(n) = 5 + 5n + 5 =⇒ S(n) = 5n + 10. (b) B(1) = 5 B(2) = 3B(1) B(3) = 3B(2) ... ... B(n) = 3B(n − 1) Multiplicando obtemos B(n) = 3 · 3 · . . . · 3B(1) = 3n−1B(1). Usando a condic¸ ˜ao b´asica temos: B(n) = 3n−1 · 5. (c) F(1) = 1 F(2) = 2F(1) + 22 F(3) = 2F(2) + 23 ... ... F(n) = 2F(n − 1) + 2n Uma soluc¸ ˜ao n˜ao nula para F(n) = 2F(n − 1) ´e F(n) = 2n−1. Fazendo F(n) = 2n−1G(n), encontramos F(1) = 20G(1) = G(1) e 2n−1G(n) = 2 · 2n−2G(n − 1) + 2n =⇒ G(n) = G(n − 1) + 2n−n+1 = G(n − 1) + 2 Somando termo a termo essa nova recorrˆencia encontramos G(n) = G(1) + 2 + 2 + . . . + 2 = G(1) + 2(n − 1) = 2n − 1 Substituindo de volta par encontrar F(n) temos G(n) = 21−nF(n) =⇒ 21−nF(n) = 2n − 1 =⇒ F(n) = 2n−1(2n − 1) (d) Uma soluc¸ ˜ao n˜ao nula de T(n) = 2T(n − 1) ´e T(n) = 2n−1. Vamos fazer a substituic¸ ˜ao T(n) = 2n−1S(n). Obtemos T(1) = 20S(1) = S(1) e 2n−1S(n) = 2 · 2n−2S(n − 1) + 1 ent˜ao S(n) = S(n − 1) + 21−n. Somando termo a termo essa nova recorrˆencia encontramos S(n) = S(1) + 2−1 + 2−2 + . . . + 21−n Usando a f´ormula da soma dos n primeiros termos da PG e a condic¸ ˜ao b´asica temos: S(n) = 1 + 2−1(2−1)n−1 − 1 2−1 − 1 = 2 − 21−n Substituindo de volta para encontrar T(n) temos T(n) = 2n−1S(n) = 2n−1(2 − 21−n) = 2n − 1 3 Matem´atica Discreta (e) A(1) = 1 A(2) = A(1) + 2 A(3) = A(2) = 3 ... ... A(n) = A(n − 1) + n Somando obtemos A(n) = 1 + 2 + 3 + . . . + n que nada mais ´e que a soma dos n da PA de primeiro termor 1 e raz˜ao 1, logo A(n) = (1 + n)n 2 = n2 + n 2 7. Quest˜ao 7 (a) No primeiro segundo, ou seja, inicialmente, s˜ao enviadas T(1) = 1000 mensagens. Como cada maquina que recebeu a mensagem no primeiro segundo transmite 10 mensagens ap´os 1 segundo, temos que no 2º segundo s˜ao enviadas T(2) = 10T(1) mensagens e assim sucessivamente. Ent˜ao a relac¸ ˜ao de recorrˆencia para o n´umero de mensagens enviadas no n-´esimo segundo ´e T(n) = 10T(n − 1), T(1) = 1000. Resolvendo temos T(1) = 1000 T(2) = 10T(1) T(3) = 10T(2) ... ... T(n) = 10T(n − 1) Multiplicando, temos T(n) = T(1) · 10 · 10 · . . . · 10 = 10n−1T(1) = 10n−1 · 103 = 10n+2 (b) No in´ıcio do 21º segundo ser˜ao enviadas T(21) = 1023 mensagens. 8. Quest˜ao 8 (a) Observando as figuras notamos que para passar de um n´umero triangular ao seguinte, precisamos juntar um lado de comprimento n. Assim temos a recorrˆencia T(n) = T(n − 1) + n, T(1) = 1. Somando termo a termo da recorrˆencia temos T(n) = 1 + 2 + 3 + 4 + . . . + n, novamente ca´ımos na soma dos n primeiros naturais, o que nos d´a T(n) = (1 + n)n 2 . 4 Matematica Discreta (b) Observando as figuras notamos que para passar de um numero pentagonal ao seguinte, precisamos juntar 3 lados de comprimento n, sendo que nas jungoes desses lados os pontos se sobrepdem, entao precisamos descontar 2 pontos dessa adicao. Assim, a recorréncia fica P(n) = P(n—1)+3n—-2,P(1) =1. Somando termo a termo temos P(n) =14+3-2—243-3-24...8n—-2=143(24+3+4+4+4+...+n)—2(n—1) P(n) =14+3(2+3+...+n)-2n+2=343(24+34+...4+n)—2n =3(14+2+...4+n)—2n Usando novamente a formula da soma dos n primeiros naturais obtemos 1 3n(1 —4 9. Questao 9 (a) A equagao caracteristica fica x” — 52 + 6 = 0, as raizes sao 2,3. Entaéo a solugao geral é T(n) = 2"C, + 3"C. Substituindo 7(1),7(2) temos 2C, + 3C, =5 1 1+ ° => 38C,=1 = O==- = Cl =2 A solugao fica: T(n) = 2"** +3". (b) A equagao caracteristica fica x” — 6x + 8 = 0, as raizes sao 2,4. Entaéo a solugao geral é A(n) = 2"C, + 4"C,. Substituindo A(1), A(2) temos 2C + 4Co = 7 1 5 4C; + 16C2 = 18 2 2 A solugao fica: A(n) = 2771-5 +4"! - 2, (c) A equacao caracteristica fica x? + 2 — 2 = 0, as raizes sao 1, —2. Entao a solugao geral fica: S(n) = C, + (—2)"C,. Substituindo $(1), S(2) temos Cy, — 2C, = 4 ' ° = 60,=-6 = G=-1 => (| =2 C, + 4C2 = —2 A solugao fica: S(n) = 2 — (—2)”. (d) A equacao caracteristica fica x? — 7x + 12 = 0, as raizes sao 3,4. Entao a solucao geral fica: P(n) = 3"C, + 4"C,. Substituindo P(1), P(2) temos 3C, + 4C, = 5 1 1+ ° = 4C¢,=2 = Cho=- = C=1 9C, + 16C, = 17 2 A solugao fica: P(n) = 3" 4+ 4""! - 2. 5 Matematica Discreta (e) A equagao caracteristica fica x” — 6x + 5 = 0, as raizes sao 1,5. Entaéo a solugao geral é F(n) = C, +5"C,. Substituindo F'(1), F'(2) temos Ci +5Cp =8 2 PPOs —= 20C,=8 = OC,== = O=6 Cy + 25C2 = 16 5 A solugao fica: F(n) =6+ 5"! - 2. (f) A equagao caracteristica fica x? + 42 + 3 = 0, as raizes sao —1, —3. Entao a solucao geral é T(n) = (-1)"C, + (—3)"C,. Substituindo 71), 7(2) temos —C) — 3C, = -1 ' ° = 6% =6 = G=1 => Cl=-2 CL +9C, =7 A solugao fica: T(n) = —2(—1)" + (—3)”. (g) A equacao caracteristica fica x? — 4x + 4 = 0, cuja Unica raiz é 2. Entao a solucao geral fica B(n) = 2"°C, + 2"nC . Substituindo B(1), B(2) temos 20) + 209 = 3 1 4C, + 802 = 14 2 A solugao fica: B(n) = —2”-' + n- 2". (h) A equagao caracteristica fica x? + 10x + 25, cuja Unica raiz 6é —5. Entao a solugao geral fica F(n) = (—5)"C, + (—5)"nC . Substituindo F'(1), (2) temos —5C, + —5C2 = —10 2 12 LF 92 —= 250,=-10 = G=-2 S G= = 25C) + 50C2 = 40 5 5 A solugao fica: (—1)” -5"~! - 12 — (—1)"- 5""! - 2n. Observe que quando dividimos por 5 e mudamos o expoente do —5 para n — 1, alteramos a paridade da poténcia, o que foi corrigindo multiplicando-se os termos por (—1)”. (i) A equagao caracteristica fica x? — 2% + 2 cujas raizes sao 1 +7 que sao complexos de modulo \/2 e argumento 6 = +" e a solucao geral fica A(n) = V2" (c: cos = + Cysen"). Substituindo $(1), S(2) temos 9 (22 +4 ca ) —8 v2(% 2 => (%=4—> CG =4 2C2 = 8 A solugao fica: A(n) = 4/2" (cos = + sen), (j) A equagao caracteristica fica x? + 47 + 5 = 0 cujas raizes sao —2 +7. O procedimento para a solugao € 0 mesmo do item anterior, exceto que nesse caso como nao teremos como argumento um angulo notavel, as contas ficam absurdas, vamos entao trabalhar com a forma algébrica. Temos a solugao geral S(n) = C\(2+7)" + C2(2 —7)", substituindo S(1), S(2) temos . . Cy +Cz=2 Cy(2 +7) + C,(2-1) =4 = => Ch =O=1 (2+ 4) + Cx(2-8) (eee 1= C2 A solugao fica: S(n) = (2+ 1)" + (2—7%)”. 6 Matem´atica Discreta 10. Quest˜ao 10 (a) O total de m´aquinas infectadas num dia n ´e T(n) = 5T(n − 1) − 1, T(1) = 3 e resolvendo obtemos T(n) = 5n−1 · 3 − 1. (b) Agora comec¸ando no dia 2, temos a recorrˆencia de limpeza que ´e S(n) = 6S(n − 1), S(2) = 1, S(1) = 0 que resolvendo d´a S(n) = 6n−2. Para saber quando as m´aquinas ficar˜ao limpas devemos ter 6n−2 ≥ 3 · 5n−1 − 1, n ≥ 3. Por inspec¸ ˜ao conclu´ımos que isso ocorre no dia 11. 7