\documentclass[12pt,a4paper]{article}

\usepackage[portuguese]{babel}
\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{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
Professor: Newton Jos\'{e} Vieira \\
\underline{Terceira Lista de Exerc\'{\i}cios/Respostas} \hfill Entrega: 30/05/2005.


\vspace*{3mm}
{\bf Seguem respostas para os exerc\'{\i}cios. Observem que uma resposta
correta  n\~ao \'e suficiente. O mais importante de uma solu\c c\~ao \'e o
\underline{processo} utilizado para se chegar at\'e a resposta!}


\vspace*{3mm}
\noindent {\bf Rela\c{c}\~{o}es de Recorr\^{e}ncia}

\begin{enumerate}
 \item $a_0=1000$, \\
       $a_n=1,05a_{n-1}-100$ para $n\geq 1$.

 \item $a_0=1$, $a_1=1$, \\
       $a_n=a_{n-1}+2a_{n-2}$ para $n\geq 2$.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=2$, \\
              $a_n=a_{n-1}+a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=3$, \\
              $a_n=2a_{n-1}+2a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, $a_1=k$, \\
              $a_n=(k-1)a_{n-1}+(k-1)a_{n-2}$ para $n\geq 2$.
       \end{list}

 \item  $a_0=1$, $a_1=1$, $a_2=1$, $a_3=2$, $a_4=3$, \\
        $a_n=a_{n-1}+a_{n-3}+a_{n-5}$ para $n\geq 5$.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=1$, $a_1=4$, \\
              $a_n=3a_{n-1}+3a_{n-2}$ para $n\geq 2$.
        \item $a_0=1$, \\
              $a_n=2a_{n-1}+4^{n-1}$ para $n\geq 1$.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=0$, \\
              $a_n=a_{n-1}+n-1$ para $n\geq 1$.
        \item $a_0=0$, \\
              $a_n=a_{n-1}+(n-1)(n-2)/2$ para $n\geq 1$.
        \item $a_0=0$, \\
              $a_n=a_{n-1}+C(n-1,k-1)$ para $n\geq 1$.
       \end{list}

 \item $d^n_0=1$, $d^1_1=1$, $d^n_n=0$ para $n>1$, \\
       $d^n_k=d^{n-1}_k+d^{n-2}_{k-1}$ para $0<k<n$.

 \item $p_0=1$, $i_0=0$, \\
       $p_n=2p_{n-1}+2i_{n-1}$ para $n\geq 1$, \\
       $i_n=2p_{n-1}+2i_{n-1}$ para $n\geq 1$.

 \item Sejam:
       \begin{enumerate}
        \item $a_n$: n\'umero de sequ\^encias com exatamente um 11;
        \item $u_n$: n\'umero de sequ\^encias com exatamente um 11, terminadas em 1;
        \item $z_n$: n\'umero de sequ\^encias com exatamente um 11, terminadas em 0;
        \item $s_n$: n\'umero de sequ\^encias sem 11.
       \end{enumerate}
       $a_n=u_n+z_n$ para $n\geq 0$, \\
       $u_n=z_{n-1}+s_{n-2}$ para $n\geq 2$,\\
       $z_n=u_{n-1}+z_{n-1}$ para $n\geq 1$, \\
       $s_n=s_{n-1}+s_{n-2}$ para $n\geq 2$. \\
       \ 
       Condi\c c\~oes de contorno: $u_0=u_1=z_0=0$, $s_0=1$, $s_1=2$.
 
 \item Basta mostrar que
       \[C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n
         -2[C_1(1+\sqrt{5})^{n-1}+C_2(1-\sqrt{5})^{n-1}]
         -4[C_1(1+\sqrt{5})^{n-2}+C_2(1-\sqrt{5})^{n-2}]\]
       \'e igual a zero.

 \item Solu\c c\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C_1(-3)^n+C_2(-2)^n$.
        \item $C_1(1-\sqrt{2})^n+C_2(1+\sqrt{2})^n$.
       \end{list}

 \item Solu\c c\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C_12^n+C_2n2^n$.
        \item $C_1(-3)^n+C_2n(-3)^n$.
       \end{list}

 \item A fun\c{c}\~{a}o geradora obtida (supondo $a_0=0$) \'e
       $g(x)=(2x-2x^2)/(1-2x)^2$. O coeficiente de $x^n$ \'e:
       $a_n=(n+1)\times 2^{n-1}$.

 \item Solu\c c\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $g(n)=C_12^n$, $p(n)=-(n^2+4n+6)$.
        \item $g(n)=C_1+C_22^n$, $p(n)=-(n^2+5n)/2$.
        \item $g(n)=C_1+C_2n$, $p(n)=n^2$.
       \end{list}

 \item Solu\c c\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $g(n)=C_1(-3)^n$, $p(n)=2^{n+1}/5$.
        \item $g(n)=C_12^n+C_2n2^n$, $p(n)=(-2)^{n-2}$.
       \end{list}

 \item Solu\c c\~oes das partes recorrentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $g(n)=C_1(-2)^n$, $p_1(n)=-(9n^2+12n+2)/27$, $p_2=2^{n-1}$.
        \item $g(n)=C_12^n$, $p(n)=n2^{n-1}$.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\sqrt[3]{2^n-1}$.
        \item $(n+2)n!$.
       \end{list}

 \item Basta resolver as rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=0$, \\
              $a_n=a_{n-1}+n$ para $n\geq 1$.
        \item $a_0=1$, \\
              $a_n=a_{n-1}+2^n$ para $n\geq 1$.
        \item $a_0=0$, \\
              $a_n=a_{n-1}+n^2$ para $n\geq 1$.
        \item $a_0=0$, \\
              $a_n=a_{n-1}+n^2+n$ para $n\geq 1$.
       \end{list}
\end{enumerate}
\end{document}

\vspace*{5mm}
\noindent{\bf Princ\'{\i}pio de Inclus\~{a}o e Exclus\~{a}o}
 
\vspace*{3mm}
 \item 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?

 \item 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?

 \item 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.

 \item 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?

 \item 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
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1\leq x_k\leq 15$
        \item $-2\leq x_k\leq 10$
        \item $k< x_k\leq 6k$
       \end{list}

 \item 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 cupon de
       cada tipo, dividido pelo n\'umero total de distribui\c c\~oes poss\'{\i}veis.)

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

 \item Em quantas permuta\c{c}\~{o}es de 1,2,\ldots, $n$, um n\'{u}mero $k$ nunca \'{e}
       imediatamente seguido de $k+1$?

 \item 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?

 \item 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?

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

 \item 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?

\end{enumerate}

\end{document}
 