\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton Jos\'{e} Vieira \hfill www.dcc.ufmg.br/\verb+~+nvieira\\
\underline{Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 02/09/2013

\vspace*{4mm}
\noindent {\bf Soma}
\begin{enumerate}
 \item[1.] Use a nota\c{c}\~ao de somat\'oria para expressar as somas:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $-5+0+5+10+\cdots+90$.
        \item $1+2+4+8+\cdots+1024$.
        \item $2+6+12+20+\cdots n(n-1)$.
        \item $1+1+4/3+8/4+16/5+\cdots+2^n/(n+1)$.
       \end{list}

% Ex. 1 pag. 328 Townsend (modificado)

\end{enumerate}
\vspace*{2mm}
\noindent {\bf Conjuntos}
 
\vspace*{2mm}
\begin{enumerate}
 \item[2.] Escreva o resultado para cada uma das express\~oes (${\cal P}(X)$ é o conjunto potência de $X$):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{1,3,5\}\cup\{1,3,6\})-\{1,4\}$.
        \item ${\cal P}(\{1,3,5\})$.
        \item $\{1,2,3\}\times\{4,5,1\}$.
        \item ${\cal P}(\{1,2\}\times\{2,4\})$.
       \end{list}

% Ex. 2 pag. 333 Townsend

 \item[3.] Em que situa\c{c}\~oes se tem as seguintes rela\c{c}\~oes entre
       os conjuntos $A$ e $B$?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cup B=A$.
        \item $A\cap B=A$.
        \item $A-B=A$.
        \item $A-B=B-A$.
       \end{list}

%      Sol. 1o semestre de 1997.

 \item[4.] Encontre todas as parti\c c\~oes do conjunto $\{a,b,c\}$.

%      Schaum: 1.23, pag. 19

 \item[5.] Prove:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\times(B\cup C)=(A\times B)\cup(A\times C)$.
        \item $A\times(B\cap C)=(A\times B)\cap(A\times C)$.
       \end{list}

% Ex. 8 pag. 334 Townsend

\end{enumerate}

\vspace*{4mm}
\noindent {\bf Rela\c c\~oes e Fun\c{c}\~oes}

\vspace*{2mm}
\begin{enumerate}
 \item[6.] Que propriedades (dentre reflexividade, simetria e transitividade)
       t\^{e}m as seguintes rela\c{c}\~{o}es?
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $R$ sobre $\{1,2,3\}$, $R=\{(1,1),(2,2),(3,3)\}$.

        \item $R$ sobre $\{1,2,3\}$, $R=\{(1,1),(1,2),(2,1),(2,2),(2,3),(3,2),(3,3)\}$.

        \item $R$ sobre todos os habitantes de BH definida por: $x R y$ se,
              e somente se, $x$ \'e um ancestral de $y$. (O ancestral pode
              ser de qualquer sexo.)

        \item $R$ sobre todos os habitantes de BH definida por: $x R y$ se,
              e somente se, $x$ \'e uma ancestral de $y$. (O ancestral \'e
              do sexo feminino.)

%             Townsend: A.2.2, ex. 2, pag. 338
        \item $\subseteq$ sobre ${\cal P}(X)$ ($X$ \'{e} um conjunto qualquer).

%             Townsend: A.2.2, ex. 3, pag. 338
        \item $R$ sobre $\bf N$ definida por: $a R b$ se, e somente se,
              $b$ \'{e} divis\'{\i}vel por $a$.

%             Townsend: A.2.2, ex. 5, pag. 338
       \end{list}

 \item[7.] Considere as seguintes rela\c{c}\~{o}es de equival\^{e}ncia:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $R_1\subseteq U\times U$: $x R_1 y \Leftrightarrow$ $x$ e $y$
              t\^{e}m o mesmo pai, sendo $U$ o conjunto
              de todos os alunos da UFMG.
        \item $R_2\subseteq\mbox{\bf N}\times\mbox{\bf N}$: $x R_2 y
              \Leftrightarrow$ $x-y \,\mbox{ mod }\, 8 =0$. 
       \end{list}
       Quais s\~ao as classes de equival\^{e}ncia induzidas por cada uma delas?

 \item[8.] Classifique (ou seja, diga se s\~{a}o injetoras, etc.) as seguintes
       fun\c{c}\~{o}es de {\bf N} para {\bf N}:      
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $f(n)=n+1$.
        \item $f(n)=n\div 2$, onde ``$\div$'' \'e divis\~ao inteira.
        \item $f(n)=n(n+1)/2$.
        \item $f(n)=n-1$ se $n$ \'e \'{\i}mpar, e $f(n)=n+1$, caso contr\'ario.
       \end{list}

%      Ex. 8 1o sem 2005

 \item[9.] D\^e uma fun\c c\~ao bijetora (correspond\^encia um-para-um) do conjunto
       dos n\'umeros naturais pares para o dos n\'umeros naturais \'{\i}mpares.

%      Townsend: A.2.2, ex. 15, pag. 339
\end{enumerate}

\vspace*{4mm}
\noindent {\bf Prova de Teoremas}

\vspace*{2mm}
\begin{enumerate}
 \item[10.] Sejam $A$, $B$, $C$ e $D$ conjuntos e suponha que $A-B\subseteq C\cap D$
       e $a\in A$. Prove que se $a\not\in D$, ent\~ao $a\in B$. Use a contrapositiva
       (prova indireta).

 %     Velleman: 3.1, ex. 4, pag. 92

 \item[11.] Suponha que $A-B\subseteq C$, e seja $x$ um elemento qualquer no
       universo. Prove, por contradi\c c\~ao, que se $x\in A-C$, ent\~ao $x\in B$.

 %     Velleman: teorema, pag. 99

 \item[12.] Prove que se $n$ \'e um n\'umero inteiro n\~ao divis\'{\i}vel por 3, ent\~ao
       $n^2=3k+1$ para algum inteiro $k$.

 \item[13.] D\^{e} uma prova indireta de que se $x^2+y^2=z^2$, ent\~{a}o pelo menos um,
       dentre $x$, $y$ e $z$, \'{e} par.

% Ex. 11 lista 1 1997
 \item[14.] Prove as leis de De Morgan para conjuntos:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\overline{A\cup B}=\overline{A}\cap\overline{B}$.
        \item $\overline{A\cap B}=\overline{A}\cup\overline{B}$.
       \end{list}

%      Townsend: A.2.1, ex. 6, pag. 333

 \item[15.] Prove que ${\cal P}(A)\cup{\cal P}(B)\subseteq {\cal P}(A\cup B)$, mas
       n\~{a}o vice-versa, isto \'{e}, nem sempre ${\cal P}(A\cup B)\subseteq
       {\cal P}(A)\cup{\cal P}(B)$.

%      Townsend: A.2.1, ex. 14, pag. 334
\end{enumerate}

\vspace*{2mm}
\noindent {\bf O princ\'{\i}pio do pombal ({\it Pigeonhole principle\/})}
 
\vspace*{2mm}
\begin{enumerate}
 \item[16.] Em qualquer grupo de $m\geq 2$ pessoas existem 2 pessoas com o
              mesmo n\'{u}meros de amigos no grupo. (Observe que siclano \'{e} amigo
              de beltrano $\Leftrightarrow$ beltrano \'{e} amigo de siclano.)
        
%             Townsend: A.3.4, ex. 17b, pag. 347
 \item[17.] Supondo que uma certa empresa tem 6 computadores, cada um
              conectado a zero ou mais dos outros computadores, ent\~{a}o existem no
              m\'{\i}nimo 2 computadores diretamente conectados ao mesmo n\'{u}mero de
              computadores.
 \item[18.] Qualquer conjunto de 7 n\'{u}meros inteiros distintos cont\'{e}m dois
              n\'{u}meros cuja soma ou diferen\c{c}a \'{e} m\'{u}ltiplo de 10.
        
%             Townsend: A.3.4, ex. 17c, pag. 347
 \end{enumerate}

\vspace*{4mm}
\noindent {\bf Um pouquinho de probabilidade}

\vspace*{2mm}
\begin{enumerate}
 \item[19.] Em um experimento de lançamento de dados, encontre as probabilidades dos seguintes eventos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Ambos os dados apresentam o mesmo número.
				\item A soma dos dois números é par.
				\item A soma é o quadrado de um dos números.
			 \end{list}

%             Tucker: A.3, ex. 3, pag. 418.
 \item[20.] Encontre a probabilidade de que na escolha aleatória de um subconjunto de dois números dentre os
       do conjunto $\{1,2,3,4,5\}$ ocorra o seguinte:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O subconjunto é $\{1,2\}$.
				\item 1 não pertence ao subconjunto.
			 \end{list}

%             Tucker: A.3, ex. 6, pag. 418.
 \item[21.] Uma urna contém 2 bolas pretas e 3 vermelhas. Se duas bolas são retiradas em sequência, qual a probabilidade
       de que ambas tenham a mesma cor?

%             Tucker: A.3, ex. 8, pag. 418.
\end{enumerate}

\vspace*{4mm}
\noindent {\bf Indu\c c\~ao Matem\'atica}

\vspace*{2mm}
\begin{enumerate}
 \item[22.] Mostre, por indu\c{c}\~{a}o, que $\sum_{k=0}^{n}(2^k)=2^{n+1}-1$ para $n\in \mbox{\bf N}$.
        
%             Townsend: 1.1, ex. 2, pag. 7
 \item[23.] Prove por indução: $\sum_{k=0}^{n}(k2^k)=(n-1)2^{n+1}+2$ para $n\in \mbox{\bf N}$.
 \item[24.] Demonstre, por indução, que $\sum_{i=0}^{n}(i\times i!)=(n+1)!-1$ para $n\in \mbox{\bf N}$.

%             Velleman: Exemplo 6.1.2, pag. 248
 \item[25.] Utilize indução matemática para mostrar que $n^3+(n+1)^3+(n+2)^3$ \'{e} divis\'{\i}vel por 9 para $n\in \mbox{\bf N}$.

%  2a lista 1997/1, Townsend, 4d, pag. 15
\end{enumerate}
 
\end{document}
