P1 - Matemática Discreta 2021-2

UFLA – ICET Departamento de Matem´atica e Matem´atica Aplicada Prof. Jamil Abreu UFLA/ICET/DMM Sala 10 Telefone: +55-35-3821-1643 E-mail: jamil.abreu@ufla.br ⋄ Matem´atica Discreta (2021/2) ⋄ — Prova 1 — 08/03/2022 Nome: Matr´ıcula: Quest˜ao 1 (15pts). Sejam A, B e C conjuntos. Mostre que (A ∪ C) ∩ (B ∪ Cc) ⊂ A ∩ B. Quest˜ao 2 (15pts). Seja R a rela¸c˜ao em Z definida por xRy se e somente se 2x+y ≡ 0 (mod 3). Mostre que R ´e uma rela¸c˜ao de equivalˆencia. Quest˜ao 3 (20pts). Seja f : X → Y uma fun¸c˜ao. Mostre que as seguintes afirma¸c˜oes s˜ao equivalentes: 1. f ´e injetora; 2. A = f −1(f(A)) para todo A ⊂ X; 3. f(X − A) ⊂ Y − f(A) para todo A ⊂ X. Quest˜ao 4 (20pts). Demonstre a seguinte identidade por indu¸c˜ao (para todo n natural): 13 + 23 + · · · + n3 = (1 + 2 + · · · + n)2. Quest˜ao 5 (15pts). A popula¸c˜ao de Belo Horizonte em 2021 era estimada em aproximadamente dois milh˜oes quinhentos e trinta mil e setecentos habitantes.(1) Estima-se que um ser humano n˜ao tenha mais do que um milh˜ao de fios de cabelos. Explique por que existia em 2021 ao menos dois belo-horizontinos com o mesmo n´umero de fios de cabelo. Quest˜ao 6 (15pts). Mostre que a seguinte rela¸c˜ao ´e uma rela¸c˜ao de ordem em R: xRy ⇐⇒ x2 < y2, ou x2 = y2 e x < y. 1Fonte: https://www.ibge.gov.br/cidades-e-estados/mg/belo-horizonte.html 1 1) ⊢ (A ∪ C) ∩ (B ∪ C^c) ⊆ A ∩ B AFIRMAÇÃO FALSA! Contra exemplo: Seja \; X = \{1, 2, 3, 4, 5 \} \; o \; universo A = \{ 1, 2, 3 \} B = \{ 2, 3, 4 \} C = \{ 3, 4, 5 \} Então \; A \cup C = \mathbb{U} X C^c = \mathbb{U} X \setminus \mathbb{A} = \{ 1, 2 \} B \cup C = \{ 2, 3, 4 \} Agora \; (A \cup C) \, \cap \; (B v C^c) = \{ 1, 2, 3, 4 \} \quad \notin A \cap B = \{2,3\} Logo \; a afirmação \; é \; falsa \; e \; a continêncââ \; não \; é \; valida. 2) R \subseteq \mathbb{Z} \times \mathbb{Z} relação : \, xRy \iff 2x+y \equiv 0 \mod 3 ⊢ R é equivalência. (i) Reflexivo. Sejam \; x \in \mathbb{Z} 2x + x \equiv 3x \equiv 0 \mod 3 \iff \; xRx \; OK! (ii) Simétrico. \; Sejam \; x, y \in \mathbb{Z} xRy \iff \; 2x+y \equiv 0 \mod 3 \iff \; 4x + 2y \equiv 0 \mod 3 \iff \; 2x + 2y \equiv 0 \mod 3 \iff \; 2y + x \equiv 0 \mod 3 \iff \; yRx \; OK! (iii) Transitivo. Sejam \; x, y, z \in \mathbb{Z} xRy \iff \; 2x+y \equiv 0 \mod 3 \iff 2x+y + 2y+z \equiv 0 \mod 3 yRz \iff \; 2y+z \equiv 0 \mod 3 \iff \; 2x + 3y + z \equiv 0 \mod 3 \iff \; 2x+z \equiv 0 \mod 3 \Rightarrow \; xRz \; OK! Como \; R \, é \, simetrico, \, reflexivo \; e \; transitivo, \; R \' \, relação \; de \; equivalência. 3) f: X \to Y \; função (i) f \; injetiva \iff \; A = f^{-1}(f(A)) \quad \forall A \subseteq X (i.i) Mostrar \; A \subseteq \; f^{-1}(f(A)) Seja \; x \in A. \; E \; não \; f(x) \notin f(A). \; Como \; f \, é \, injetiva f^{-1}(f(x)) = x \in f^{-1}(f(A)). (i.ii) Mostrar \; f^{-1}(f(A)) \subseteq \, A Seja \; x \in f^{-1}(f(A)) \; \Rightarrow \; \exists y \in f(A) \; tq \; y = f(x). Como \; y \in f(A) \; e \; y = f(x) \; Segue \; que \; x \in A. Logo \; por \; vale \; \left( \subseteq \right) e \; \left( \supseteq \right) , \; vale \; a \; igualdade. b) \; A = f^{-1}(f(A)) \quad \Rightarrow \; f(X-A) \subseteq \; Y - f(A) \; \forall A \subseteq X Seja \; y \in f(x-A). \; Então \; temos \; que \exists x \in X-A \; tal \, que f(x) = \tilde{y}. Por \; definição, \; y \in \mathbb{F} (X) = Y. Por \; absurdo, \; suponha \; que \; y \in f(A), \; Isto \; implica \; que \exists x \in A tq \; y = f(x) \; e \; y = f(x) \implies \; f (x) = f(x) \implies \; f(\left\{x \right\} ) = \left\{ x\right\} , \; portanto \; x=x = \; e \in \; \mathbb{E} (X-A), \; x \in \mathbb{E} A, \; absurdo, Logo \; y \notin f(A) Então \; y \in \; Y \; mas \; y \notin f(A) \; : \; y \in \; Y - f(A) c) \mathbb{F} (X-A) \subseteq \; Y - f(A), \; \forall A \subseteq X \quad \Rightarrow \; f \, injeta Sejam \; x_2, \, x_1 \in E \setminus X \, e \, A = \left\{x \right\} e \; x \neq x_1. Denotando \; \tilde{y} = f(x) \, e \, \tilde{y} = f(x_1), \; temos \; , \; por \, hipótese \mathbb{F} (X - \left\{ x_1 \right\}) \subseteq \mathbb{F} (X) - \mathbb{F} (x_1) Logo, \; sendo \; \tilde{y} = f(\tilde{x} ) \quad \, \tilde{y i} \in \; \mathbb{F} (X - \left\{ x_1 \right\} ) \, ima \; x \neq x_1, Então \; y \in \mathbb{F} (X) - \mathbb{F} (x_1) Logo \; \tilde{y} \notin \mathbb{F} (\left\{ ilde{x} \right\} ) \; e \; portanto \tilde{y i} \neq \mathbb{F} (\tilde{y} = \; y Concluimos \; que \; x \neq x_2 \quad \Rightarrow \; f(x) \neq f(x_1), f \; é \; injetora 4) 1³ + 2³ + 3³ + ... + n³ = (1 + 2 + ... + n)² Por indução: *(Base da indução): Se n = 1: 1³ = 1² OK! Se n = 2: 1³+3³ = 9 = (1²)² OK! Vale para n = 1 e para n = 2 *Passo indutivo: (Hipótese de indução): 1³ + 2³ + ... + k³ = (1 + 2 + ... + K)² Vale para algum K∈N Vamos usar a soma 1 + 2 + ... + K = \frac{K(K+1)}{2} (Soma de Progressão Aritmética) Note que 1 + 2 + ... + K + (K + 1) = \frac{(K+1)(K+2)}{2} Então (1 + 2 + ... + K + (K+1))² = \frac{(K+1)(K+2)}{4} Por outro lado, temos que \sum_{i=1}^{K} i³ = \frac{K²(K+1)²}{4}, Formula da soma cúbica. Portanto \sum_{i=1}^{K+1} i = \frac{(K+1)²(K+2)²}{4} = (1 + 2 + 3 + ... + k + (K+1))² Logo \frac{(K+1)²((K+1)+1)²}{4} = (1 + 2 + ... + k + (K+1))² Portanto se vale para K∈N, vale para K+1, Conclui-se indução, vale para todo K∈N. Em síntese, há mais pessoas do que possibilidades de fios de cabelo. De maneira mais elaborada, suponha que todas as pessoas tivessem uma quantidade diferente de fios de cabelo na cidade e no ano especificados. Então vamos escolher primeiro a pessoa com zero fios. Depois a com 1 fio. Depois a com 2 fios. E vamos ordenando, de um em um. Quando chegarmos na última pessoa, que terá 1000000 fios de cabelo, teremos esgotado a quantidade máxima de cabelo, embora haja ainda mais de um milhao de pessoas restando para serem contadas. Haverá repetição, irrefutavelmente, de numero de fios. Para ser relação de ordem deve ser reflexiva, antissimetrica e transitiva. Falha a reflexiva.