Exame de Matemática Discreta: combinatória, grafos, números e recursões

Apuntes

Matemática Discreta 2024/2025 Universidade de Évora Exame, época normal Justifique todas as respostas. 1. Um chefe de cozinha quer contratar dois cozinheiros e três ajudantes de co- zinha. a) De um conjunto de 17 candidatos (a ambas as funções), quantas equipas diferentes pode formar? b) O João Fazbolos é dos candidatos. Quantas equipas o incluem? 2. a) Diga, justificando, se os seguintes grafos são isomorfos: 1 3 4 5 2 6 G a b c d e f H b) Existe algum caminho de Hamilton no grafo G? c) Quantos subgrafos de H com 6 vértices e 6 arestas existem? d) Algum dos subgrafos de H referidos na alínea anterior é uma árvore? 3. a) Utilize o algoritmo de Euclides para encontrar o máximo divisor co- mum entre 165 e 57 e para encontrar inteiros s e t tais que s · 57 + t · 165 = d, onde d = mdc(165, 57). b) Encontre um divisor de zero em Z 165 . c) Considere a igualdade 1 = 2 · 23 − 5 · 9. Encontre um natural r, com 0 ≤ r < 23, tal que r é o inverso de 9 em Z 23 . 4. Recorde a definição por recorrência da sucessão de Lucas: L 0 = 2, L 1 = 1 e, para qualquer n ∈ N, L n+2 = L n+1 + L n . Considere a sucessão (t n ) n∈N dada recursivamente por t 0 = 3, t n+1 = 1 + 1 t n , n ∈ N. Mostre por indução ...