\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} -- \underline{Solu\c{}\~oes da Parte 2}: \underline{Princ\'{\i}pio de Inclus\~{a}o e Exclus\~{a}o}

\vspace*{2mm}
\begin{enumerate}
 \item {\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 {\footnotesize Dentre os n\'{u}meros de 1 a 1000, inclusive, quantos s\~{a}o divis\'{\i}veis por
       2, 5 ou 12? Quantos n\~{a}o s\~{a}o divis\'{\i}veis por 5, nem por 6, nem por 8?}

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

       Seja, considerando o universo $U$ dos n\'umeros de 1 a 1000, $D_i$ o conjunto dos n\'umeros
       divis\'{\i}veis por $i$. Ent\~ao:
       \begin{itemize}
        \item $N(D_2\cup D_5\cup D_{12})=N(D_2\cup D_5)$, pois $D_{12}\subsetq D_2$. E
              $N(D_2\cup D_5)=(1000/2+1000/5-1000/10=500+200-100=600$.
         \item $N(\overline{D_5}\cap\overline{D_6}\cap\overline{D_8})=N(U)-N(D_5\cup D_6\cup D_8)=
               1000-[(1000/5+1000/6+1000/8)-(1000/30+1000/40+1000/24)+1000/120]=
               1000-[(200+166+125)-(33+25+41)+8]=1000-(491-99+8)=1000-406=594$.
       \end{itemize}

 \item {\footnotesize Encontre o n\'{u}mero de sequ\^{e}ncias de tamanho $k$, tomadas do conjunto
       $\{a_1, a_2, \ldots, a_n\}$, em que cada $a_i$ aparece pelo menos uma
       vez em cada sequ\^{e}ncia.}

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

       Seja $U$ o conjunto de todas as sequ\^encias de $k$ elementos do conjunto $\{a_1, a_2, \ldots, a_n\}$.
       Seja $S_i$ o conjunto das sequ\^encias de $k$ elementos em que $a_i$ aparece pelo menos uma
       vez. Pede-se $N(S_1\cap S_2\cap \ldots\cap S_n)$, que \'e igual a $N(U)-N(\overline{S_1}\cup 
       \overline{S_2}\cup \ldots\cup \overline{S_n})$. Como:
       \begin{itemize}
        \item $N(U)=n^k$;
        \item $N(\overline{S_i})=(n-1)^k$;
        \item $N(\overline{S_i}\cap\overline{S_j})=(n-2)^k$ para $j\not=i$;
        \item etc.
       \end{itemize}
       tem-se:
       \[N(S_1\cap S_2\cap \ldots\cap S_n)=n^k-[\binom{n}{1}(n-1)^k-{n\choose 2}(n-2)^k+\cdots+
        (-1)^n{n\choose n}(n-n)^k]\mbox{.}\]
       Logo, $N(S_1\cap S_2\cap \ldots\cap S_n)=\sum_{i=0}^{n}(-1)^iC(n,i)(n-i)^k$.

 \item {\footnotesize Quantos arranjos existem das letras A,A,A,B,B,B,C,C,C, nos quais n\~{a}o
       apare\c{c}am 3 letras consecutivas id\^{e}nticas?}

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

       Sejam $A$ o conjunto dos arranjos em que aparecem 3 As consecutivos, $B$ o conjunto dos arranjos
       em que aparecem 3 Bs consecutivos e $C$ o conjunto dos arranjos em que aparecem 3 Cs consecutivos. 

       Ent\~ao, $N(\overline{A}\cap\overline{B}\cap\overline{C})=N(U)-N(A\cup B\cup C)$. Logo,
       \[N(\overline{A}\cap\overline{B}\cap\overline{C})=P(9;3,3,3)-({3 \choose 1}P(7;3,3,1)-
         {3 \choose 2}P(5;3,1,1)+{3 \choose 3}P(3;1,1,1))\mbox{.}\]
       Portanto,
       \[N(\overline{A}\cap\overline{B}\cap\overline{C})=\frac{9!}{3!^3}-(3\frac{7!}{3!^2}-
         3\frac{5!}{3!}+3!)\mbox{.}\]

 \item {\footnotesize Usando o princ\'{\i}pio da inclus\~{a}o e exclus\~{a}o, determine o n\'{u}mero de
       solu\c{c}\~{o}es inteiras para $x_1+x_2+x_3+x_4=20$, se $-2\leq x_k\leq 10$.}

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

       O n\'umero de solu\c{c}\~oes \'e o mesmo que o de $y_1+y_2+y_3+y_4=28$ com $0\leq y_i\leq 12$.
       Seja $Y_i$ o conjunto das ``solu\c{c}\~oes'' desta \'ultima em que $y_i\leq 12$, mas $y_j$, para
       $i\not=j$, podendo tomar qualquer valor a partir de 0 (inclusive maior que 12). Ent\~ao, o
       n\'umero de solu\c{c}\~oes procurado \'e $N(Y_1\cap Y_2\cap Y_3\cap Y_4)$. Tem-se:
       \[N(Y_1\cap Y_2\cap Y_3\cap Y_4)={4-1+28\choose 28}-[{4\choose 1}{4-1+15\choose 15}-
         {4\choose 2}{4-1+2\choose 2}+0-0]\mbox{.}\]

 \item {\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 {\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 {\footnotesize Em quantas permuta\c{c}\~{o}es de 1,2,\ldots, $n$, um n\'{u}mero $k$ nunca \'{e}
       imediatamente seguido de $k+1$?}

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

       Seja $P_i$ o conjunto de permuta\c{c}\~oes em que $k$ n\~ao \'e seguido de $k+1$.
       Pede-se $N(P_1\cap P_2\cap \ldots\cap P_{n-1})$. Tem-se:
       \[N(P_1\cap P_2\cap \ldots\cap P_{n-1})=n!-[{n-1\choose 1}(n-1)!-{n-1\choose 2}(n-2)!+\cdots
         +(-1)^{n}{n-1\choose n-1}0!]\mbox{,}\]
       ou seja,
       \[N(P_1\cap P_2\cap \ldots\cap P_{n-1})=\sum_{k=0}^{n-1}(-1)^k{n-1\choose k}(n-k)!\mbox{.}\]

% \item {\footnotesize De quantos modos 6 casais podem sentar-se ao redor de uma mesa circular
%       de tal forma que marido e mulher n\~{a}o fiquem juntos?}

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

%       Seja $C_i$ o conjunto de disposi\c{c}\~oes da mesa em que o casal $i$ fique separado.
%       Pede-se $N(C_1\cap C_2\cap \ldots\cap C_6)$. Tem-se:
%       \[N(C_1\cap \ldots\cap C_6)=11!-[{6\choose 1}.2.10!-{6\choose 2}.2^2.9!+{6\choose 3}.2^3.8!
%         -{6\choose 4}.2^4.7!+{6\choose 5}.2^5.6!-{6\choose 6}.2^6.5!]\mbox{.}\]

 \item {\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{.}\]

 \item {\footnotesize De quantas maneiras podemos permutar os d\'{\i}gitos 1, 2, 3, 4, 5, 6, 7, 8, 9
       de forma que nenhum d\'{\i}gito par fique em sua posi\c{c}\~{a}o natural?}

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

       Seja $A_p$ o conjunto dos arranjos em que o d\'{\i}gito par $p$ aparece em sua posi\c{c}\~{a}o natural.
       Pede-se, ent\~ao, $N(\overline{A_2}\cap\overline{A_4}\cap\overline{A_6}\cap\overline{A_8})$
       Tem-se:

       \[N(\overline{A_2}\cap\overline{A_4}\cap\overline{A_6}\cap\overline{A_8})=9!-
         [{4\choose 1}8!-{4\choose 2}7!+{4\choose 3}6!-{4\choose 4}5!]\mbox{.}\]
\end{enumerate}

\end{document}
