\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{amsmath}

\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{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \hfill nvieira@dcc.ufmg.br\\
\underline{Terceira Lista de Exerc\'{\i}cios} -- Para voc\^e conferir \\
\underline{Princ\'{\i}pio de Inclus\~{a}o e Exclus\~{a}o} --- N\~ao resolvidos na \'ultima aula.

\vspace*{2mm}
\begin{enumerate}
 \item[1.] {\footnotesize Numa cidade em que s\~{a}o publicados os jornais A, B e C, foram obtidos
       os seguintes resultados numa pesquisa: 20\% da popula\c{c}\~{a}o l\^{e} o jornal
       A, 16\% o jornal B, 14\% o jornal C; 8\% l\^{e} A e B, 5\% A e C e 4\% B
       e C. Somente 2\% l\^{e} os tr\^{e}s jornais. Qual a porcentagem da
       popula\c{c}\~{a}o que n\~{a}o l\^{e} nenhum destes tr\^{e}s jornais?}

       \textit{Solu\c{c}\~ao}:

       Sejam, considerando um universo, $U$, de 100 leitores:
       \begin{itemize}
        \item $A$: conjunto dos leitores do jornal $A$;
        \item $B$: conjunto dos leitores do jornal $B$; e
        \item $C$: conjunto dos leitores do jornal $C$.
       \end{itemize}
       S\~ao dados: $N(A)=20$, $N(B)=16$, $N(C)=14$, $N(A\cap B)=8$, $N(A\cap C)=5$, $N(B\cap C)=4$ e
       $N(A\cap B\cap C)=2$.

       $N(\overline{A}\cap\overline{B}\cap\overline{C})=N(U)-N(A\cup B\cup C)=100-(20+16+14-8-5-4+2)=100-35=65$.
       Logo, 65\% da popula\c{c}\~{a}o n\~{a}o l\^{e} nenhum dos tr\^{e}s jornais.
         

 \item[6.] {\footnotesize Uma companhia de sab\~{a}o em p\'{o} oferece 3 tipos diferentes de cupons em
       suas caixas de sab\~{a}o. Cada caixa cont\'{e}m um cupom; se voc\^{e} colecionar
       pelo menos um de cada tipo, voce ganha um brinde. Qual \'{e} a probabilidade
       de voc\^{e} ganhar um brinde, se voc\^{e} comprar 10 caixas? (A probabilidade \'e
       o n\'umero de distribui\c c\~oes poss\'{\i}veis em que aparece pelos um cupom de
       cada tipo, dividido pelo n\'umero total de distribui\c c\~oes poss\'{\i}veis.)}

       \textit{Solu\c{c}\~ao}:

       Seja $U$ o conjunto de todas as sequ\^encias dos n\'umeros 1, 2 e 3.
       Seja $C_i$ o conjunto das sequ\^encias dos n\'umeros 1, 2 e 3 em que o n\'umero $i$
       ocorre pelo menos uma vez. Ent\~ao a probabilidade pedida \'e $N(C_1\cap C_2\cap C_3)/N(U)$.
       Como $N(U)=3^{10}$ e
       \[N(C_1\cap C_2\cap C_3)=N(U)-N(\overline{C_1}\cap \overline{C_2}\cap \overline{C_3}=
         3^{10}-[{3\choose 1}2^{10}-{3\choose 2}1^{10}+{3\choose 3}0]=3^{10}-3.2^{10}+3\]
       segue-se que a probabilidade ser\'a:
       \[\frac{3^{10}-3.2^{10}+3}{3^{10}}=1-\frac{2^{10}-1}{3^{9}}\mbox{.}\]

 \item[7.] {\footnotesize Oito pessoas entram em um elevador, no primeiro andar. O elevador descarrega
       passageiros em cada um dos andares seguintes (no m\'{\i}nimo, um passageiro por
       andar), at\'{e} ficar vazio no quinto andar (ap\'{o}s descarregar, no
       m\'{\i}nimo, um passageiro). Determine, usando o princ\'{\i}pio da inclus\~{a}o e
       exclus\~{a}o, de quantas maneiras diferentes isto pode acontecer.}

       \textit{Solu\c{c}\~ao}:

       Seja $D_i$ o conjunto de distribui\c{c}\~oes das 8 pessoas em que o $i$-\'esimo andar
       recebe pelo menos uma delas. Pede-se $N(D_2\cap D_3\cap D_4\cap D_5)$. Tem-se:

       \[N(D_2\cap D_3\cap D_4\cap D_5)=4^8-[{4\choose 1}3^8-{4\choose 2}2^8+{4\choose 3}1^8
         -{4\choose 4}0]=4^8-[4.3^8-6.2^8+4]\mbox{.}\]

 \item[9.] {\footnotesize Quantas maneiras existem de arranjar as letras em REDIVIDERS de forma
       que apare\c{c}a pelo menos um par de letras consecutivas id\^{e}nticas?}

       \textit{Solu\c{c}\~ao}:

       Apenas R, E, D e I podem ser repetidas. Seja R o conjunto dos arranjos em que aparece RR,
       E o conjunto dos arranjos em que aparece EE etc. Pede-se, ent\~ao, $N(R\cup E\cup D\cup I)$.
       Tem-se:
       \[N(R\cup E\cup D\cup I)={4\choose 1}\frac{9!}{2!^3}-{4\choose 2}\frac{8!}{2!^2}
         +{4\choose 3}\frac{7!}{2!}-{4\choose 4}6!\mbox{.}\]

\end{enumerate}

\end{document}
