\documentclass[12pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

%\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Primeira Prova}/Solução do professor \hfill 4/9/2013

%\vspace*{1mm}
\begin{enumerate}
 \item {\footnotesize Sobre somatória:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Avalie: $\sum_{k=-3}^{5}(k^2-2)$.
        \item Expresse usando a notação de somatória: $1+8+27+64+\cdots+n^3$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item $\sum_{k=-3}^{5}(k^2-2)=((-3)^2-2)+((-2)^2-2)+((-)1^2-2)+(0^2-2)+(1^2-2)+(2^2-2)+(3^2-2)+(4^2-2)+(5^2-2)=
				       7+2-1-2-1+2+7+14+23=51$.
        \item $\sum_{k=1}^{n}k^3$.
       \end{list}
 \item {\footnotesize Seja um grupo de 20 pessoas, 13 das quais do sexo feminino. Suponha que 8 destas pessoas do sexo
       feminino sejam casadas (não necessarimente com pessoas do grupo). Em cada um dos casos a seguir,
       diga se a situação apontada é possível. Em caso positivo, indique o número de \emph{pessoas do sexo
			 masculino casadas}.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
 %       \item Há 12 pessoas que são casadas ou são do sexo feminino (ou são ambos).
        \item Há 8 pessoas solteiras.
        \item Há 15 pessoas que são do sexo feminino ou são solteiras (ou ambos).
        \item Considerando apenas as pessoas do sexo masculino, o número de casadas é idêntico ao de solteiras.
       \end{list}
       \emph{Dica}: comece fazendo um diagrama mostrando as 4 partes obtidas
			 considerando-se sexo (masculino ou feminino) e situação matrimonial (casado ou solteiro).}

       \textit{Solução:}

       Há 13 pessoas do sexo feminino e, portanto, $20-13=7$ do sexo masculino. Das 13 pessoas do sexo feminino, 8
			 são casadas e, portanto, $13-8=5$ são solteiras. Denotando-se por $x$ e $y$ os números de pessoas do sexo
			 masculino casadas e solteiras, tem-se o seguinte diagrama que sintetiza as informações:
       
       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,41)
         \put(33,0){\framebox(50,36){}}
         \put(58,0){\line(0,1){36}}
         \put(33,18){\line(1,0){50}}
         \put(45.5,37){\makebox(0,0)[b]{\textbf{casados}}}
         \put(70.5,37){\makebox(0,0)[b]{\textbf{solteiros}}}
         \put(32,27){\makebox(0,0)[r]{\textbf{fem:} 13}}
         \put(32,9){\makebox(0,0)[r]{\textbf{masc:} 7}}
         \put(45.5,27){\makebox(0,0)[c]{$8$}}
         \put(70.5,27){\makebox(0,0)[c]{$5$}}
         \put(45.5,9){\makebox(0,0)[c]{$x$}}
         \put(70.5,9){\makebox(0,0)[c]{$y$}}
        \end{picture}
       }

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Sabe-se que $y+5=8$. Logo, $y=3$ e $x=7-3=4$.
        \item Sabe-se que $13+y=15$. Logo, $y=2$ e $x=7-2=5$.
				\item Situação impossível: como $x+y=7$, é impossível ter $x=y$.
       \end{list}

 \item {\footnotesize Que propriedades, dentre reflexividade, simetria e transitividade, têm as seguintes relações?
       Diga também quais são relações de equivalência.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item $R$ sobre $\{1,2,3\}$, $R=\{(1,1),(2,2),(3,3)\}$.
        \item $R$ sobre todos os alunos da UFMG, definida por: $x R y \,\Leftrightarrow\, x$ é mais velho que $y$.
        \item $R$ sobre ${\cal P}(X)$ ($X$ \'{e} um conjunto finito qualquer), definida por:  $x R y \,\Leftrightarrow\,$
				      o número de elementos do conjunto $x$ é menor ou igual ao de $y$.
        \item $R$ sobre ${\cal P}(X)$ ($X$ \'{e} um conjunto finito qualquer), definida por:  $x R y \,\Leftrightarrow\,$
				      $x$ e $y$ têm o mesmo número de elementos.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Não reflexiva, não simétrica, transitiva.
        \item Reflexiva, não simétrica, transitiva, se $X\not=\emptyset$. Se $X=\emptyset$, $R$ é reflexiva,
				      simétrica e transitiva.
        \item Reflexiva, simétrica, transitiva.
       \end{list}
			 A última é relação de equivalência. A penúltima também, se $X=\emptyset$.
 \item {\footnotesize Em certo torneio de tênis, há uma fase inicial em que cada um dos jogadores joga com todos os outros
       exatamente uma vez. Suponha que cada jogador vence pelo menos uma partida. Mostre que ao final da fase pelo menos dois
			 jogadores terão vencido o mesmo número de partidas.}

       \textit{Solução:}

       Suponha que o torneio tenha $n$ jogadores. Já que cada jogador vence pelo menos uma partida, segue-se que cada jogador
			 vence de 1 a $n-1$ partidas. Como são $n$ jogadores, cada um podendo vencer de 1 a $n-1$ partidas, pelo princípio
			 da casa de pombos pelo menos dois jogadores terão vencido o mesmo número de partidas.		 
 \item {\footnotesize Uma caixa contém 3 bolas verdes, 4 amarelas e 5 azuis. Se três bolas são retiradas em sequência, qual 
       a probabilidade de que a primeira seja amarela, a segunda azul e a terceira verde?}

       \textit{Solução:}

       Como são $3+4+5=12$ bolas, o espaço amostral contém $12\times 11\times 10=1320$ eventos elementares. O número
			 destes eventos em que a primeira bola é amarela, a segunda azul e a terceira verde é: $4\times 5\times 3=60$. Logo, a
			 probabilidade é $60/1320=1/22$.
 \item {\footnotesize Mostre, usando indução matemática, que a soma dos $n$ primeiros números ímpares é $n^2$, ou seja,
       $\sum_{k=1}^{n}(2k-1)=n^2$ para todo $n\geq 1$.}

       \textit{Solução:}
\enlargethispage{1cm}
       $\sum_{k=1}^{1}(2k-1)= 2\times 1-1=1=1^2$. Seja $n$ um número natural arbitrário tal que $n\geq 1$. Suponha, como
			 hipótese de indução, que $\sum_{k=1}^{n}(2k-1)=n^2$. Basta mostrar que $\sum_{k=1}^{n+1}(2k-1)=(n+1)^2$. Tem-se:
			 \begin{tabbing}
			 xxx\= $\sum_{k=1}^{n+1}(2k-1)$\=$=\sum_{k=1}^{n}(2k-1)\,+\,2(n+1)-1$ x\=    \kill
			    \> $\sum_{k=1}^{n+1}(2k-1)$\>$=\sum_{k=1}^{n}(2k-1)\,+\,2(n+1)-1$ \> pela definição de $\sum$ \\
			    \>                         \>$=n^2+2(n+1)-1$ \> pela hipótese de indução \\
			    \>                         \>$=n^2+2n+1$ \\
			    \>                         \>$=(n+1)^2$. \\
			 \end{tabbing}
\end{enumerate}

\end{document}
