\documentclass[12pt,a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Matem\'atica Computacional \hfill DCC/ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira \\
\underline{Quarta Lista de Exerc\'{\i}cios}: {\bf Combinat\'{o}ria Elementar}

\vspace*{2mm}
\noindent {\bf Importante:} Em todas as quest\~oes deve-se indicar o {\em processo\/} usado para
determinar cada solu\c c\~ao. {\em O processo \'e mais importante do que a solu\c c\~ao.\/}
``Continhas'' s\~ao desnecess\'arias.

\begin{enumerate}
 \item Duas cartas de baralho s\~ao distribu\'{\i}das para uma pessoa. Para cada $k= 0, 1, 2$
       determine o n\'umero de distribui\c c\~oes com exatamente $k$ ases.

 \item Quantas vezes ocorre a subsequ\^encia 13 quando se lista os inteiros de 1 a 10000?

 \item Quantas maneiras existem de distribuir um \'as, depois uma carta vermelha e, em seguida,
       uma carta preta? E se, adicionalmente, n\~ao aparece nenhum par (duas cartas de
       mesmo n\'umero)?

 \item De quantas maneiras se pode arranjar as letras em EMPILHAR:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item no total?
        \item com todas as vogais consecutivas?
        \item com M antes de (n\~ao necessariamente encostado em) P? 
        \item com exatamente duas letras entre M e P? 
       \end{list}

 \item Uma lanchonete fornece sandu\'{\i}ches com quaisquer dentre 9 ingredientes adicionais,
       al\'em da carne (um sandu\'{\i}che pode ter de zero a todos os 9 ingredientes).
       Quantos pedidos diferentes s\~ao poss\'{\i}veis?

 \item Uma moeda \'e lan\c cada 50 vezes e produz 20 caras. De quantas maneiras isto podeu\'{\i}che
       ocorrer?

 \item De quantas maneiras se pode colocar 5 homens e 5 mulheres sentados lado a lado, de
       forma que homens n\~ao fiquem juntos?

 \item Um aluno de Computa\c c\~ao tem 7 livros diferentes de linguagens em uma prateleira,
       3 de C e 4 de Java. De quantas formas ele pode dispor os livros na prateleira, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item n\~ao h\'a restri\c c\~oes?
        \item as linguagens devem alternar?
        \item Os livros C devem ficar todos juntos?
        \item Os livros C devem ficar todos juntos e os de Java tamb\'em?
       \end{list}

 \item Dez pessoas s\~ao selecionadas para compor um time de {\em softball\/}, a partir de
       um grupo de 15 homens e 8 mulheres. Quantos times s\~ao poss\'{\i}veis com
       exatamente 4 mulheres? E com no m\'{\i}nimo 4 mulheres? E com no m\'{\i}nimo tantas
       mulheres quantos homens?

 \item Doze pratos est\~ao pendurados em 4 colunas, como mostra a
       seguinte figura:
       
       \begin{picture}(200,126)(-80,0) \footnotesize
        \put(0,106){\line(1,0){200}}
        \put(0,116){\line(1,0){200}}
        \put(0,106){\line(0,1){10}}
        \put(200,106){\line(0,1){10}}
       
        \put(37,17){\circle{14}}
        \put(37,17){\makebox(0,0){V}}
        \put(37,24){\line(0,1){10}}
        \put(37,41){\circle{14}}
        \put(37,41){\makebox(0,0){V}}
        \put(37,48){\line(0,1){10}}
        \put(37,65){\circle{14}}
        \put(37,65){\makebox(0,0){V}}
        \put(37,72){\line(0,1){10}}
        \put(37,89){\circle{14}}
        \put(37,89){\makebox(0,0){V}}
        \put(37,96){\line(0,1){10}}
        \put(37,106){\circle*{4}}
       
        \put(79,41){\circle{14}}
        \put(79,41){\makebox(0,0){B}}
        \put(79,48){\line(0,1){10}}
        \put(79,65){\circle{14}}
        \put(79,65){\makebox(0,0){B}}
        \put(79,72){\line(0,1){10}}
        \put(79,89){\circle{14}}
        \put(79,89){\makebox(0,0){B}}
        \put(79,96){\line(0,1){10}}
        \put(79,106){\circle*{4}}
       
        \put(121,65){\circle{14}}
        \put(121,65){\makebox(0,0){P}}
        \put(121,72){\line(0,1){10}}
        \put(121,89){\circle{14}}
        \put(121,89){\makebox(0,0){P}}
        \put(121,96){\line(0,1){10}}
        \put(121,106){\circle*{4}}
       
        \put(163,41){\circle{14}}
        \put(163,41){\makebox(0,0){A}}
        \put(163,48){\line(0,1){10}}
        \put(163,65){\circle{14}}
        \put(163,65){\makebox(0,0){A}}
        \put(163,72){\line(0,1){10}}
        \put(163,89){\circle{14}}
        \put(163,89){\makebox(0,0){A}}
        \put(163,96){\line(0,1){10}}
        \put(163,106){\circle*{4}}
       \end{picture}
       
       Como se pode ver, existem 4 pratos vermelhos na primeira coluna, 3
       brancos na segunda, 2 pretos na terceira e 3 azuis na quarta. Para ser
       admitida na equipe de tiro da sua Escola, Matilde tem que quebrar os 12
       pratos usando um rev\'olver e apenas 12 balas. Em certo instante, ela
       s\'o pode quebrar o prato mais baixo de alguma coluna (ou seja, apenas 1
       prato pode ser quebrado de cada vez). Sob estas condi\c c\~oes,
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item de quantas maneiras pode Matilde quebrar os 12 pratos?
        \item de quantas maneiras Matilde poderia quebrar os 12 pratos,
              quebrando inicialmente todos os vermelhos e pretos, antes de
              quebrar algum prato das outras cores?
        \item de quantas maneiras Matilde poderia quebrar os 12 pratos sem
              quebrar 2 brancos consecutivamente?
       \end{list}

 \item No sistema Braille, um s\'{\i}mbolo \'e representado por {\it
       pelo menos uma\/} sali\^encia no arranjo de 6 pontos mostrados na parte
       (a) da seguinte figura:
       
       \begin{picture}(200,90)(-50,0)
        \put(30,15){\makebox(0,0){(a)}}
        \put(5,24){\line(1,0){50}}
        \put(5,80){\line(1,0){50}}
        \put(5,24){\line(0,1){56}}
        \put(55,24){\line(0,1){56}}
        \put(12,37){\makebox(0,0){\footnotesize 3}}
        \put(20,37){\makebox(0,0){\circle*{1}}}
        \put(48,37){\makebox(0,0){\footnotesize 6}}
        \put(40,37){\makebox(0,0){\circle*{1}}}
        \put(12,52){\makebox(0,0){\footnotesize 2}}
        \put(20,52){\makebox(0,0){\circle*{1}}}
        \put(48,52){\makebox(0,0){\footnotesize 5}}
        \put(40,52){\makebox(0,0){\circle*{1}}}
        \put(12,67){\makebox(0,0){\footnotesize 1}}
        \put(20,67){\makebox(0,0){\circle*{1}}}
        \put(48,67){\makebox(0,0){\footnotesize 4}}
        \put(40,67){\makebox(0,0){\circle*{1}}}

        \put(120,15){\makebox(0,0){(b)}}
        \put(120,30){\makebox(0,0){``c''}}
        \put(95,24){\line(1,0){50}}
        \put(95,80){\line(1,0){50}}
        \put(95,24){\line(0,1){56}}
        \put(145,24){\line(0,1){56}}
        \put(102,37){\makebox(0,0){\footnotesize 3}}
        \put(110,37){\circle*{1}}
        \put(138,37){\makebox(0,0){\footnotesize 6}}
        \put(130,37){\circle*{1}}
        \put(102,52){\makebox(0,0){\footnotesize 2}}
        \put(110,52){\circle*{1}}
        \put(138,52){\makebox(0,0){\footnotesize 5}}
        \put(130,52){\circle*{1}}
        \put(102,67){\makebox(0,0){\footnotesize 1}}
        \put(110,67){\circle*{4}}
        \put(138,67){\makebox(0,0){\footnotesize 4}}
        \put(130,67){\circle*{4}}


        \put(210,15){\makebox(0,0){(c)}}
        \put(210,30){\makebox(0,0){``t''}}
        \put(185,24){\line(1,0){50}}
        \put(185,80){\line(1,0){50}}
        \put(185,24){\line(0,1){56}}
        \put(235,24){\line(0,1){56}}
        \put(192,37){\makebox(0,0){\footnotesize 3}}
        \put(200,37){\circle*{4}}
        \put(228,37){\makebox(0,0){\footnotesize 6}}
        \put(220,37){\circle*{1}}
        \put(192,52){\makebox(0,0){\footnotesize 2}}
        \put(200,52){\circle*{4}}
        \put(228,52){\makebox(0,0){\footnotesize 5}}
        \put(220,52){\circle*{4}}
        \put(192,67){\makebox(0,0){\footnotesize 1}}
        \put(200,67){\circle*{1}}
        \put(228,67){\makebox(0,0){\footnotesize 4}}
        \put(220,67){\circle*{4}}


        \put(300,15){\makebox(0,0){(d)}}
        \put(300,30){\makebox(0,0){``;''}}
        \put(275,24){\line(1,0){50}}
        \put(275,80){\line(1,0){50}}
        \put(275,24){\line(0,1){56}}
        \put(325,24){\line(0,1){56}}
        \put(282,37){\makebox(0,0){\footnotesize 3}}
        \put(290,37){\circle*{4}}
        \put(318,37){\makebox(0,0){\footnotesize 6}}
        \put(310,37){\circle*{1}}
        \put(282,52){\makebox(0,0){\footnotesize 2}}
        \put(290,52){\circle*{4}}
        \put(318,52){\makebox(0,0){\footnotesize 5}}
        \put(310,52){\circle*{1}}
        \put(282,67){\makebox(0,0){\footnotesize 1}}
        \put(290,67){\circle*{1}}
        \put(318,67){\makebox(0,0){\footnotesize 4}}
        \put(310,67){\circle*{1}}

       \end{picture}
       
       Assim, por exemplo, a letra ``c'' \'e representada por sali\^encias nos
       pontos 1 e 4, como mostra a parte (b) da figura; a letra ``t'' \'e
       representada por sali\^encias nos pontos 2, 3, 4, e 5, como mostra a
       parte (c); e o ``;'' \'e representado por sali\^encias nos pontos 2 e 3,
       como mostra a parte (d).
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantos s\'{\i}mbolos t\^em exatamente 3 sali\^encias?
        \item Quantos s\'{\i}mbolos t\^em um n\'umero par de sali\^encias?
        \item Quantos s\'{\i}mbolos podem ser representados no sistema Braille?
       \end{list} 

 \item Quantos {\em bytes\/} cont\^em (a) exatamente dois 1's; (b) exatamente seis
       1's; (c) pelo menos seis 1's?

 \item Quatro n\'umeros devem ser selecionados do conjunto $\{-5,-4,-3,
       -2,-1,1,2,3,4\}$. De quantas maneiras podem ser feitas as sele\c c\~oes
       de forma que o produto dos 4 n\'umeros seja positivo e
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item os n\'umeros selecionados sejam distintos?
        \item cada n\'umero possa ser selecionado at\'e 4 vezes?
        \item cada n\'umero possa ser selecinado at\'e 3 vezes?
       \end{list}

 \item O sargento Garcia deve distribuir 40 balas, 20 para rifles e
       20 para rev\'olveres, entre 4 oficiais, de forma que cada oficial receba
       no m\'{\i}nimo 2 e no m\'aximo 7 balas de cada tipo. De quantas maneiras
       ele pode fazer a distribui\c c\~ao?

 \item De quantas maneiras se pode distribuir $n$ objetos distintos em $n$
       caixas distintas, de forma que nenhuma caixa fique vazia? E de forma que
       exatamente uma caixa fique vazia?

 \item Quantas maneiras existem de distribuir $r$ bolas id\^{e}nticas em $n$
       caixas distintas, ficando exatamente $v$ caixas vazias?

 \item Um {\it closet\/} cont\'{e}m 6 pares de sapatos. Quantas sele\c c\~oes e
       quantos arranjos existem de 4 destes sapatos, caso:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item nenhum par completo seja escolhido?
        \item 2 pares completos sejam escolhidos?
       \end{list}

 \item Qual a probabilidade de que 12 pessoas escolhidas aleatoriamente fa\c cam anivers\'ario
       em meses diferentes? E que fa\c cam anivers\'ario no mesmo m\^es? Assuma 365 dias no ano.

 \item $n$ pauzinhos, cada um de uma cor, s\~ao quebrados em duas partes, uma maior e outra
       menor. Quantas maneiras h\'a de combinar os $2n$ peda\c cos em $n$ pares de forma que
       cada par consista de um peda\c co menor e um maior?

 \item Quantas sequ\^{e}ncias tern\'{a}rias de 30 d\'{\i}gitos t\^{e}m exatamente dez 1's?

 \item Cartas s\~ao colocadas uma a uma sobre uma mesa. De quantas maneiras pode acontecer
       do $k$-\'esimo \'as ser a $r$-\'esima carta a ser colocada sobre a mesa?

 \item Quantos arranjos das letras de EMPERRAMENTO n\~{a}o t\^em vogais consecutivas?


 \item Encontrar o n\'{u}mero de solu\c{c}\~{o}es em inteiros n\~{a}o-negativos
       para o sistema de equa\c{c}\~{o}es:
       
       \[\left. \begin{array}{l}
                 x_1+x_2+x_3+x_4+x_5\leq 20 \\
                 x_1+x_2+x_3=10
                \end{array} \right\} \mbox{ com } x_k\geq k \]

 \item Qual \'{e} o coeficiente de $x^9y^3w^6$ em $(x+y+z+w)^{18}$?

 \item Prove que \[\sum_{k=0}^{n}\left(\begin{array}{c} n \\
                                        k
                                       \end{array} \right) 2^k=3^n\mbox{.}\]
       {\em Dica\/}: use o Teorema Binomial.

 \item Derive a identidade $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$ a partir do
       Teorema Binomial.

 \item Prove, usando racioc\'{\i}nio combinat\'{o}rio:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(2n,n)=\sum_{k=0}^{n}C(n,k)^2$
        \item $C(m+n,r)=\sum_{k=0}^{r}C(m,k)C(n,r-k)$
       \end{list}
\end{enumerate}
 
\end{document}
