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) $\not\supseteq (A \cup C) \cap (B \cup C^{c}) \subseteq A \cap 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 = \{ 1, 2, 3, 4, 5 \} = X$ $C^{c} = X \backslash C = \{ 1, 2 \}$ $B \cup C^{c} = \{ 2, 3, 4 \}$ Agora $(A \cup C) \cap (B \cup C^{c}) = \{ 1, 2, 3, 4 \} \not \subseteq A \cap B = \{ 2, 3 \}$ Logo a afirmação é falsa e a continência não é válida. "(usei \subseteq para contido) não confundir com letra C" 2) $R \subseteq \mathbb{Z} \times \mathbb{Z}$ relação : $xRy \iff 2x+y \equiv 0 \mod 3$ $R$ é equivalência. (i) Reflexivo. Seja $x \in \mathbb{Z}$ $2x + x \equiv 3x \mod 3 \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 x+y \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+2y+2z \equiv 0 \mod 3$ $yRz \iff 2y+z \equiv 0 \mod 3$ $\Rightarrow 2x + 3y + z \equiv 0 \mod 3 \Rightarrow 2x+z \equiv 0 \mod 3$ $\Rightarrow xRz$, OK! "Como $R$ é simétrico, reflexivo e transitivo, $R$ é relação de equivalência." 3) $F : X \rightarrow Y$ Função (a) $F$ injetiva $\Rightarrow A = F^{-1}(F(A)) \ \forall A \subseteq X$ (i) Mostrar $A \subseteq F^{-1}(F(A))$ Seja $x \in A$. É nítido que $F(x) \in F(A)$. Como $F$ é injetiva, $F^{-1}(F(x)) = x \in F^{-1}(F(A))$. (ii) Mostrar $F^{-1}(F(A)) \subseteq A$ Seja $x \in F^{-1}(F(A))$. Então $\exists y \in F(A)$ t.q. $y = F(x)$. Como $y \in F(A)$, $\exists y = F(x)$, segue que $x \in A$. Logo, por valer $\subseteq$ e $\supseteq$, vale a igualdade. (b) $\displaystyle A = F^{-1}(F(A)) \ \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) = y$. Por definição, $y \notin F(X) = Y$. Por absurdo, supomos agora que $y \in F(A)$. Isto implica que $\exists x \in A$ t.q. $y = F(x)$ e $y = F(x)$, mas $F^{-1}(F(\{x\})) = \{x\}$, portanto $x = x_1, x \in X-A, x_2 \in A$, absurdo. Logo $y \notin F(A)$ Então $y \in Y$ mas $y \notin F(A)$ : $y \in Y - F(A)$ (c) $F(X-A) \subseteq Y-F(A), \ \forall A \subseteq X \Rightarrow F \text{ injetiva}$ Sejam $x, x' \in X$ e $A = \{ x \}$ e $x \neq x'$. Denotando $y = F(x)$ e $y' = F(x')$, temos, por hipótese $F(X - \{ x \}) \subseteq F(X) - F(\{x\})$ Logo, sendo $y' = F(x')$, $y' \in F(X - \{ x \})$ pois $x \neq x'$. Então $y \in F(X) - F(\{ x \})$ Logo $y' \notin F(\{ x \})$ e portanto $y' \neq F(x) = y$ Concluímos que $x \neq x' \Rightarrow F(x) \neq F(x')$, F é injetiva. 4) 1^3+2^3+3^3+...+n^3=(1+2+...+n)^2 Por indução: * (Base da indução): se n=1 : 1^3=1^2 OK! se n=2 : 1^3+3^3=9=(1+2)^2 OK! Vale para n=1 e para n=2 * Passo indutivo. (Hipótese de indução): 1^3+2^3+...+k^3=(1+2+...+k)^2 Vale para algum k∈N Vamos usar a Soma 1+2+...+k=k(k+1)/2 (Soma de Progressão Aritmética) Note que 1+2+...+k+(k+1)=(k+1)(k+2)/2 Então (1+2+...+k+(k+1))^2=(k+1)(k+2)^2/4 Por outro lado, temos que ∑_(i=1)^(k) i^3=(k^2.(k+1)^2)/4 (Fórmula da soma cúbica), Portanto ∑_(i=1)^(k+1) i^3=((k+1)^2.(k+2)^2)/4=(1+2+3+...+k+(k+1))^2 Logo ((k+1)^2((k+1)+1)^2)/4=(1+2+...+k+(k+1))^2 Portanto, se vale para k∈N, vale para k+1. Conclui-se a indução, vale para toda 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. ∴ Se (x^2=y^2 e x<y) e (y^2<z^2), então x^2<z^2 logo xRz se (x^2=y^2 e x<y) e (y^2=z^2 e y<z), então x^2=y^2=z^2 e x<y<z, logo (x^2=z^2 e x<z) logo xRz. Então R é relação de ordem ESTRITA.