Matemática

Instituto Federal de Educacao Ciˆencia e Tecnologia Campus Crato Avaliacao N2 Matematica Discreta Moesio 1 Alun Instrucoes As questoes valem 0 50 ponto cada Resposta sem resolucao nao sera considerada no momento da correcao Entrega fısica dia 25082025 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 M Matrıcula 1 Considere um grafo cujos vertices sao V 0 1 2 3 4 5 6 7 8 e as arestas vem da sequˆencia de vertices dos ultimos 8 dıgitos de sua matrıcula D7 D8 D9 D10 D11 D12 D13 D14 A Matrıcula a Desenhe o grafo b Esse grafo e conexo c Esse grafo tem um caminho hamiltoniano d Esse grafo tem um caminho euleriano e Esse grafo e hamiltoniano f Esse grafo e euleriano 2 Prove que todo grafo G possui um numero par de vertices de grau ımpar 3 Quantas arestas tem um grafo com vertices de graus 5 2 2 2 2 1 Desenhe um possıvel grafo 4 Mostre por inducao que n 3n para todo natural n com n 7 5 Se xn1 xn 4n e x1 3 determine a xn b x10 6 Se xn1 n3 xn x1 3 Determine a xn b x10 7 Dada equacao xn1 n 1xn 4n x1 5 a Determine xn Sugestao Use a formula n n1 1 n 1 n1 b Determine x10 8 Dada equacao xn1 n2xn n 12 x1 2 a Determine xn 1moesioifceedubr IFCE 1 20 de agosto de 2025 Instituto Federal de Educacao Ciˆencia e Tecnologia Campus Crato b Determine x10 9 Se x1 3 e para n 1 xn1 6xn 4 determine o valor de xn em funcao de n 10 Se x1 2 e para n 1 xn1 5xn 7 determine o valor de xn em funcao de n 11 Considerando a recorrˆencia xn1 7xn1 12xn 0 x0 1 x2 3 a Determine xn b Determine x10 12 O DNA de um aluno de discreta e formado por sequˆencias de cinco proteınas chamadas 0 1 c x e y Nas sequˆencias nunca aparecem cx cy yx e yy Todas as outras possibilidades sao permitidas a Quantas sao as possıveis sequˆencias de DNA de um aluno de discreta com n proteınas Solucao Sejam an a quantidade de sequˆencias de n proteınas que nao terminam com c ou y e bn a quantidade de sequˆencias que terminam com c ou y Queremos xn an bn b Quantas sao as possıveis sequˆencias de DNA de um aluno de discreta com 10 proteınas 13 Considerando a recorrˆencia 2xn1 13xn1 11xn 0 x0 1 x2 3 a Determine xn b Determine x10 14 Numa disputa de estilingue Chico pode fazer em cada etapa 1 ou 2 a De quantos modos ele pode totalizar n pontos Sugestao Chame de xn o numero de modos de obter n pontos e tente determinar os modos de se obter n 2 pontos b De quantos modos ele pode totalizar 10 pontos 15 Um determinado processador PIC foi projetado para receber uma determinada quantidade de vari aveis de entrada De acordo com o projeto na sua saıda ocorrera sequˆencias pertencentes a 0 1 de tamanho arbitrario e deve ser evitada sequˆencias ımpares de valores 1 Seja xn a quantidade de sequˆencias de tamanho n conforme descrito acima a Determine xn b Determine x10 16 Considerando D9 D10 D11 D12 D13 D14 R Matrıcula seja R 13 textse D9 D10 D10 D10 D10 D10 D10 4 15 textse 4 D9 D10 D10 D10 D10 D10 D10 8 17 textse 8 D9 D10 D10 D10 D10 D10 D10 12 19 textse 12 D9 D10 D10 D10 D10 D10 D10 16 21 textse 16 D9 D10 D10 D10 D10 D10 D10 20 Durante a guerra de judeus e romanos Josephus estava entre rebeldes judeus encurralados em uma caverna pelos romanos Preferindo o suicıdio a captura os rebeldes decidiram formar um cırculo e contando ao longo deste suicidase uma pessoa sim uma nao ate nao sobrar ninguem IFCE 2 20 de agosto de 2025 Instituto Federal de Educacao Ciˆencia e Tecnologia Campus Crato a Se na caverna estavam R rebeldes Determine qual posicao Josephus deveria escolher para sair ileso desse cırculo malıgno b Se na caverna estavam n rebeldes Determine qual posicao Josephus deveria escolher para sair ileso desse cırculo malıgno 17 Considerando D9 D10 D11 D12 D13 D14 T Matrıcula seja T o conjunto formado pelos seis ultimos dıgitos de sua matriculaObs conjunto nao tem algarismos repetidos Determine o numero de sequˆencias de 10 termos pertencentes ao conjunto T que nao possuem dois termos consecutivos iguais a 0 18 Considerando D9 D10 D11 D12 D13 D14 T Matrıcula seja n D9 D10 D11 e m D12 D13 D14 Resolva xn1 nxn m 19 1 Ponto Considerando D9 D10 D11 D12 D13 D14 T Matrıcula seja k D9 D10 D11 e w D12 D13 D14 Resolva xn2 kxn1 wxn 0 IFCE 3 20 de agosto de 2025 C Esse grafo tem um caminho hamiltoniano Um caminho hamiltoniano é um caminho que visita cada vértice exatamente uma vez Um possível caminho hamiltoniano é 5031 Portanto sim o grafo tem um caminho hamiltoniano d Esse grafo tem um caminho euleriano Um caminho euleriano é um caminho que visita cada aresta exatamente uma vez Para que um grafo tenha um caminho euleriano ele deve ter no máximo dois vértices de grau ímpar Vértice 5 grau 1 Vértice 0 grau 3 Vértice 1 grau 3 Vértice 3 grau 1 Como o grafo tem quatro vértices de grau ímpar ele não tem um caminho euleriano 1 a b Esse grafo é conexo Sim o grafo é conexo pois existe um caminho entre qualquer par de vértices e Esse grafo é hamiltoniano Um grafo hamiltoniano é um grafo que possui um ciclo hamiltoniano ou seja um ciclo que visita cada vértice exatamente uma vez exceto o vértice inicial que é visitado duas vezes no início e no fim do ciclo Um possível ciclo hamiltoniano é 50315 Portanto sim o grafo é hamiltoniano f Esse grafo é euleriano Um grafo euleriano é um grafo que possui um ciclo euleriano ou seja um ciclo que visita cada aresta exatamente uma vez Para que um grafo seja euleriano todos os seus vértices devem ter grau par Como nem todos os vértices têm grau par o grafo não é euleriano Seja G V E um grafo onde V é o conjunto de vértices e E é o conjunto de arestas Denotamos por dv o grau do vértice v que é o número de arestas incidentes a v Pelo Lema do Aperto de Mão Handshaking Lemma temos que a soma dos graus de todos os vértices em um grafo é igual ao dobro do número de arestas vV dv 2E Como 2E é um número par a soma dos graus de todos os vértices também deve ser par Agora vamos dividir o conjunto de vértices V em dois subconjuntos Vpar e Vi mpar onde Vpar contém os vértices de grau par e Vi mpar contém os vértices de grau ímpar Assim podemos reescrever a soma dos graus como vV dv vVpar dv vVi mpar dv V em dois subconjuntos Vpar e Vi mpar onde Vpar contém os vértices de grau par e Vi mpar contém os vértices de grau ímpar Assim podemos reescrever a soma dos graus como vV dv vVpar dv vVi mpar dv Como a soma total vV dv é par e a soma dos graus dos vértices de grau par vVpar dv também é par pois cada dv é par então a soma dos graus dos vértices de grau ímpar vVi mpar dv deve ser par para que a soma total seja par Seja n o número de vértices em Vi mpar Se n fosse ímpar então a soma vVi mpar dv seria uma soma de um número ímpar de números ímpares o que resultaria em um número ímpar No entanto sabemos que vVi mpar dv deve ser par Portanto n deve ser par Assim provamos que o número de vértices de grau ímpar em um grafo G deve ser par 2E 5 2 2 2 2 1 2E 14 E 7 4 Para n 7 7 7 6 5 4 3 2 1 5040 37 3 3 3 3 3 3 3 2187 Como 5040 2187 a desigualdade é verdadeira para n 7 Hipótese Indutiva Assumimos que a desigualdade é verdadeira para algum k 7 ou seja k 3k Passo Indutivo Precisamos mostrar que a desigualdade é verdadeira para n k 1 ou seja k 1 3k1 Começamos com o lado esquerdo da desigualdade que queremos provar k 1 k 1 k Usando a hipótese indutiva k 3k podemos escrever k 1 k 1 3k Agora precisamos mostrar que k 1 3k 3k1 Dividindo ambos os lados por 3k obtemos k 1 3 Como k 7 então k 1 8 e portanto k 1 3 é verdadeiro Assim temos k 1 k 1 3k 3 3k 3k1 Portanto k 1 3k1 Conclusão Pelo princípio da indução matemática a desigualdade n 3n é verdadeira para todo natural n 7 5 a Para encontrar uma expressão para xn podemos analisar a relação de recorrência dada xn1 xn 4n Dado que x1 3 podemos escrever os primeiros termos da sequência para identificar um padrão x2 x1 41 3 4 7 x3 x2 42 7 8 15 x4 x3 43 15 12 27 Podemos expressar xn como uma soma telescópica xn x1 Σk1n1 4k xn 3 4 Σk1n1 k Usando a fórmula para a soma dos primeiros n 1 inteiros Σk1n1 k n1n2 temos xn 3 4 n1n2 xn 3 2nn 1 xn 3 2n2 2n xn 2n2 2n 3 Portanto a expressão para xn é xn 2n2 2n 3 b Para encontrar x₁₀ substituímos n 10 na expressão que encontramos para xₙ x₁₀ 210² 210 3 x₁₀ 2100 20 3 x₁₀ 200 20 3 x₁₀ 180 3 x₁₀ 183 Portanto x₁₀ 183 6 a Para determinar xₙ podemos expressar os primeiros termos da sequência e procurar um padrão x₁ 3 x₂ 1³ x₁ 1 3 4 x₃ 2³ x₂ 8 4 12 x₄ 3³ x₃ 27 12 39 Observando a sequência podemos generalizar xₙ como xₙ n 1³ n 2³ 1³ x₁ Como x₁ 3 podemos escrever xₙ k1 ⁿ¹ k³ 3 Usando a fórmula da soma dos cubos dos primeiros n 1 números naturais k1 ⁿ¹ k³ n 1 n 2² Portanto xₙ n 1 n 2² 3 b Para encontrar x₁₀ substituímos n 10 na fórmula que encontramos x₁₀ 10 1 10 2 ² 3 x₁₀ 9 10 2 ² 3 x₁₀ 90 2² 3 x₁₀ 45² 3 x₁₀ 2025 3 x₁₀ 2028 Assim x₁₀ 2028 7 a Determine xn A equação dada é xn1 n 1xn 4n com x1 5 nn1 1n 1n1 xn1n1 n1xnn1 4nn1 xn1n1 xnn 4nn1 yn1 yn 4nn1 yn1 yn 4 1n 1n1 yn1 yn 4 1n 1n1 n 1 n k 1 sumn1k1 yn1 yn sumn1k1 4 1n 1n1 yk y1 4 11 1k Como x1 5 temos y1 x11 51 5 Substituindo y1 na equação yk 5 4 1 1k yk 9 4k Agora substitua yk xkk para encontrar xk xkk 9 4k xk 9k 4 Portanto xn 9n 4 b Determine x10 Agora vamos calcular x10 usando a fórmula que encontramos x10 910 4 x10 93628800 4 x10 32659200 4 x10 32659196 Assim x10 32659196 8 a Determine xn xn 1 nn12n16 n 12 b Determine x10 y10 1 1011216 1 385 386 92 131 681 894 400 x10 386 92 50 829 211 238 400 xn16xn xnhA6n1 C6C4 5C4 C45 xnA6n1 45 x1A60 45A 453 xn1956n1 45 1 Encontre os primeiros termos para identificar um padrão x12 x25x1752717 x35x27517792 x45x375927467 2 Tente encontrar uma solução da forma xnA5nB Substitua xn e xn1 na relação de recorrência A5n1B5A5nB7 A5n1BA5n15B7 Simplifique para encontrar B B5B7 4B7 B74 3 Use a condição inicial x12 para encontrar A x1A51 742 5A2748474154 A154534 4 Escreva a fórmula explícita para xn xn345n 74 Portanto o valor de xn em função de n é xn35n 74 a Determine xn A recorrência dada é xn2 7xn1 12xn0 com x01 e x23 1 Equação Característica A equação característica associada é r2 7r 120 2 Raízes da Equação Característica Fatorando a equação temos r3r40 As raízes são r13 e r24 3 Solução Geral Como as raízes são distintas a solução geral é da forma xnA3n B4n 4 Determinar as Constantes A e B Usamos as condições iniciais para encontrar A e B Para n0 x01 1A30 B40A B Para n2 x23 3A32 B429A 16B 5 Resolver o Sistema de Equações Temos o sistema A B 1 9A 16B 3 Multiplicando a primeira equação por 9 temos 9A 9B 9 9A 16B 3 Somando as equações 7B 6 B 67 Substituindo B na primeira equação A 67 1 A 1 67 137 6 Solução Particular Portanto a solução é xn 137 3n 67 4n b Determine x10 Agora calculamos x10 usando a fórmula encontrada x10 137 310 67 410 x10 137 59049 67 1048576 x10 7676377 62914567 x10 767637 62914567 x10 55238197 x10 789117 Portanto x10 789117 12 a Quantas são as possíveis sequências de DNA de comprimento n an nº de sequências de tamanho n que não terminam com c nem y bn nº de sequências de tamanho n que terminam com c ou y Logo total xn an bn xn an bn 3xn1 2an1 Substituindo an1 3xn2 xn 3xn1 6xn2 Condições iniciais Para n 1 qualquer proteína pode aparecer 5 opções x1 5 x2 21 xn satisfaz xn 3xn1 6xn2 x1 5 x2 21 b Para n 10 x1 5 x2 21 x3 321 65 63 30 93 x4 393 621 279 126 405 x5 3405 693 1215 558 1773 x6 31773 6405 5319 2430 7749 x7 37749 61773 23247 10638 33885 x8 333885 67749 101655 46494 148149 x9 3148149 633885 444447 203310 647757 x10 3647757 6148149 1943271 888894 2832165 13 a Determinar xn A recorrência dada é 2xn2 13xn1 11xn 0 com x0 1 e x2 3 2r2 13r 11 0 2r 11r 1 0 r1 1 r2 112 xn A1n B112n Para n 0 x0 A10 B1120 A B 1 Para n 2 x2 A12 B1122 A B1214 3 A B 1 A 1214 B 3 1214 B B 3 1 1174 B 2 B 8117 A 1 B 1 8117 117117 8117 109117 xn 1091171n 8117112n xn 109117 8117112n b Determinar x10 x10 109117 8117 11210 Calculando o valor x10 109117 8117 259374246011024 x10 109117 8 25937424601 117 1024 x10 109117 207499396808119808 x10 109117 207499396808119808 173298813 14º a Para totalizar n pontos Chico pode fazer isso de duas maneiras 1 Fazendo 1 ponto na última etapa Nesse caso ele precisava ter n1 pontos antes O número de maneiras de chegar a n1 pontos é xn1 2 Fazendo 2 pontos na última etapa Nesse caso ele precisava ter n2 pontos antes O número de maneiras de chegar a n2 pontos é xn2 Portanto o número total de maneiras de chegar a n pontos é a soma das maneiras de chegar a n1 e n2 pontos Isso nos dá a seguinte relação de recorrência xn xn1 xn2 Para iniciar a sequência precisamos de dois valores iniciais x1 1 apenas uma maneira de fazer 1 ponto 1 x2 2 duas maneiras de fazer 2 pontos 11 ou 2 b Para totalizar 10 pontos podemos usar a relação de recorrência que encontramos na parte a e calcular os valores sucessivos até chegar a x10 x3 x2 x1 2 1 3 x4 x3 x2 3 2 5 x5 x4 x3 5 3 8 x6 x5 x4 8 5 13 x7 x6 x5 13 8 21 x8 x7 x6 21 13 34 x9 x8 x7 34 21 55 x10 x9 x8 55 34 89 Portanto existem 89 maneiras de Chico totalizar 10 pontos 15º a Determine xn Seja an o número de sequências de tamanho n que terminam com 0 e bn o número de sequências de tamanho n que terminam com 1 Então temos xn an bn As relações de recorrência são an1 an bn uma sequência que termina em 0 pode ser estendida por 0 ou 1 bn1 an uma sequência que termina em 1 só pode ser estendida por 0 para evitar um número ímpar de 1s consecutivos Com as condições iniciais a1 1 a sequência é 0 b1 1 a sequência é 1 Podemos então expressar xn em termos de números de Fibonacci Observe que x1 a1 b1 1 1 2 x2 a2 b2 a1 b1 a1 1 1 1 3 Isso sugere que xn é o n2ésimo número de Fibonacci Portanto xn Fn2 onde Fn é o nésimo número de Fibonacci b Determine x10 Para encontrar x10 precisamos encontrar o 12º número de Fibonacci F12 Os números de Fibonacci são 1 1 2 3 5 8 13 21 34 55 89 144 Então F12 144 16 D9 2 D10 0 D11 8 D12 5 D13 0 D14 3 Agora somamos os dígitos de D9 a D14 S 2 0 8 5 0 3 18 Consultando as condições para R Se S 4 então R 13 Se 4 S 8 então R 15 Se 8 S 12 então R 17 Se 12 S 16 então R 19 Se 16 S 20 então R 21 Como 16 18 20 temos que R 21 a Para R 21 rebeldes Jn 2l 1 onde n 2m l e 0 l 2m Para n 21 encontramos o maior 2m menor ou igual a 21 que é 24 16 Então m 4 e l 21 16 5 J21 2 5 1 11 Portanto Josephus deve escolher a posição 11 para sobreviver b Para n rebeldes A posição que Josephus deve escolher é dada pela fórmula geral Jn 2l 1 onde n 2m l e 0 l 2m Aqui m é o maior inteiro tal que 2m n e l n 2m 17 Conjunto T sem repetição 0 1 3 9 Para terminar com nãozero 139 3 escolhas após qualquer sequência válida de tamanho n 1 3Aₙ₁ Para terminar com 0 o penúltimo deve ser nãozero então vem de uma sequência válida de tamanho n 1 que termina com nãozero que são 3Aₙ₂ Logo Aₙ 3Aₙ₁ 3Aₙ₂ A₁ 4 A₂ 15 Calculando até n 10 A₁₀ 641520 18 D₉ 0 D₁₀ 1 D₁₁ 0 D₁₂ 3 D₁₃ 1 D₁₄ 9 n D₉ D₁₀ D₁₁ 0 1 0 1 m D₁₂ D₁₃ D₁₄ 3 1 9 13 xₖ₁ n xₖ m Como n 1 a relação fica xₖ₁ xₖ 13 19 20222085010319 D9 5 D10 0 D11 1 D12 0 D13 3 D14 1 k D9 D10 D11 5 0 1 6 w D12 D13 D14 0 3 1 4 A equação de recorrência é xₙ₂ kxₙ₁ wxₙ 0 Substituindo os valores de k e w temos xₙ₂ 6xₙ₁ 4xₙ 0 r² 6r 4 0 r b b² 4ac 2a Onde a 1 b 6 e c 4 r 6 6² 414 21 r 6 36 16 2 r 6 52 2 r 6 213 2 r 3 13 Então as duas raízes são r₁ 3 13 r₂ 3 13 xₙ A3 13ⁿ B3 13ⁿ