P2 - Matemática Discreta 2021 2

UFLA – ICET Departamento de Matemática e Matemática Aplicada Prof. Jamil Abreu UFLA/ICET/DMM Telefone: +55-35-3821-1643 E-mail: jamil.abreu@ufla.br ⋄ Matemática Discreta (2021/2) ⋄ — Prova 2 — 26/04/2022 Nome: __________________________________________ Matrícula: ________________ Questão 1 (20pts). Mostre que ℘(N) e {0, 1}^N têm a mesma cardinalidade. Questão 2 (20pts). Seja (a_n)_n∈N uma sequência de números reais. O produto \prod_{k=1}^n a_k é definido “recursivamente” por \prod_{k=1}^1 a_k = a_1, \prod_{k=1}^{n+1} a_k = \left(\prod_{k=1}^n a_k\right) a_{n+1}. Torne esta definição rigorosa por uma aplicação do teorema da definição recursiva. (O produto \prod_{k=1}^n a_k é frequentemente denotado por a_1 ⋯ a_n.) Questão 3 (20pts). Mostre que se b|a, c|a e (b, c) = 1 então bc|a. Questão 4 (20pts). Ache a solução geral da equação Diofantina linear 2072x + 1813y = 2849. Questão 5 (20pts). Um agência bancária possui cinco gerentes de conta, quatro contadores e oito funcionários de caixa. Uma comissão interna de sete pessoas deve ser formada para discutir um assunto interno. De quantas maneiras esta comissão pode ser formada sob a condição de que haja dois gerentes, dois contadores e três caixas? Olá cliente! Segue o seu material resolvido! Além das soluções alguns exercícios acompanham notas explicativas que facilitarão seus estudos. Agradeço por ter me escolhido para lhe ajudar. Ah... se possível deixe seu comentário em meu perfil. Atenciosamente Guru Jéssica - Via meuguru.net Questão 1 (20pts). Mostre que ℘(N) e {0, 1}^N têm a mesma cardinalidade. Nota explicativa: Entendendo o enunciado: ℘(N) é o conjunto das partes de \mathbb{N}, ou seja, é o conjunto dos subconjuntos de \mathbb{N}. ℘(N) = {∅, {1}, {2}, ..., {1,2}, ... } {0,1}^N é o produto cartesiano (0,1) x (0,1) x (0,1) .... Em uma quantidade infinita \mathbb{N}. Ou seja: X ∈ {0,1}^N => X = (a_1, a_2, ..., a_n, ...), a_i∈{0,1} Demostrar que dois conjuntos possuem a mesma cardinalidade é equivalente a provar que é possível construir uma bijeção entre eles. Questão 2 (20pts). Seja (a_n)_{n ∈ N} uma sequência de números reais. O produto \prod_{k=1}^n a_k é definido “recursivamente” por \prod_{k=1}^1 a_k = a_1, \prod_{k=1}^{n+1} a_k = (\prod_{k=1}^n a_k) a_{n+1}. Torne esta definição rigorosa por uma aplicação do teorema da definição recursiva. (O produto \prod_{k=1}^n a_k é frequentemente denotado por a_1 \cdots a_n.) A definição torna-se rigorosa quando escrevemos: P(g) = g(n) \cdot a_{m+1} onde g: \{1, \ldots, m\} \to \mathbb{R} \left\{ f(n+1) = f(n) \cdot a_{n+1} f(1) = a_1 \right. Por exemplo os conjuntos N e Z possuem mesma cardinalidade, basta associar cada natural par a um inteiro positivo e cada natural ímpar a um inteiro negativo: 0 0 1 -1 2 1 3 -2 4 2 5 -3 6 3 A relação acima é uma bijeção, portanto \mathbb{N} e \mathbb{Z} tem mesma cardinalidade. Solução: Construir um subconjunto de \mathbb{N} é equivalente a escolher para cada elemento de \mathbb{N} se ele pertencerá ou não há este subconjunto. Portanto podemos associar este subconjunto a uma sequência ordenada de zeros e uns de modo que cada elemento x_i corresponde a 1, se i está no subconjunto e 0 caso contrário. Por exemplo: \emptyset \to (0,0,0,\ldots) \{1\} \to (1,0,0,0,\ldots) \{1,3,5\} \to (1,0,1,0,1,0,0,0,\ldots) Portanto é possível construir uma bijeção entre \mathcal{P}(\mathbb{N}) e \{0,1\}^{\mathbb{N}}, donde podemos concluir que possuem mesma cardinalidade. Questão 3 (20pts). Mostre que se b|a, c|a e (b, c) = 1 então bc|a. Nota explicativa: A notação b|a lê-se b divide a, portanto é equivalente à dizer que a é um múltiplo de b, o que pode ser escrito como: a = b.k, com k∈ℤ. Essa escrita torna mais “palpável” algumas demonstrações sobre divisibilidade. Questão 3 (20pts). Mostre que se b|a, c|a e (b, c) = 1 então bc|a. - Como b|a, temos: a = b.k1, k1∈ℤ ① - Como c|a, então: a = c.k2, k2∈ℤ ② De ① e ②, podemos concluir que: b.k1 = c.k2 E como (b, c) = 1, podemos garantir que k2 = b.k, k∈ℤ Substituindo em ②, temos: a = c.b.k ⇒ bc|a □ Questão 4 (20pts). Ache a solução geral da equação Diofantina linear 2072x + 1813y = 2849. 1º Passo: Utilizar o algoritmo de Euclides para determinar o MDC dos coeficientes. (2072, 1813) 2072 = 1813.1 + 259 * 1813 = 259.7 + 0 MDC 2º Passo: Utilizar as equações acima para escrever o MDC como uma combinação linear dos coeficientes. Neste caso, trivial, pois * 2072 = 1813.1 + 259 2072.1 + 1813.(-1) = 259 x0 y0 Ou seja, encontramos uma solução particular (x₀, y₀) = (1, -1) 3º Passo: Escrever a solução geral: A solução é sempre da forma: {x = x₀ + b t y = y₀ - a t Onde: "b" é o coeficiente de y, "a" é o coeficiente de x. Solução geral: {x = 1 + 1813t y = -1 - 2072t Questão 5 (20pts). Um agência bancária possui cinco gerentes de conta, quatro contadores e oito funcionários de caixa. Uma comissão interna de sete pessoas deve ser formada para discutir um assunto interno. De quantas maneiras esta comissão pode ser formada sob a condição de que haja dois gerentes, dois contadores e três caixas? Desejamos "escolher" dois gerentes, ou seja: C_{5,2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{5.4.3!}{2.3!} = 10 E "escolher" dois contadores: C_{4,2} = \frac{4!}{2!(4-2)!} = \frac{4!}{2!2!} = \frac{4.3.2!}{2.2!} = 6 E também "escolher" três caixas: C_{8,3} = \frac{8!}{3!(8-3)!} = \frac{8!}{3!5!} = \frac{8.7.6.5!}{3.2.5!} = 56 O total de comissões é o produto destes resultados: 10.6.56 = 3360 comissão.