\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} \hfill Entrega: 30/05/2005.

\noindent {\bf Rela\c{c}\~{o}es de Recorr\^{e}ncia}

\begin{enumerate}
 \item Um certo banco est\'a cobrando 5\% de juros ao m\^es. Tadeu tomou
       emprestados R\$1.000,00, e deve pagar presta\c c\~oes mensais fixas de
       R\$100,00 (a primeira ao final do primeiro m\^es de empr\'estimo).
       Encontre uma rela\c c\~ao de recorr\^encia para a d\'{\i}vida de Tadeu ao
       final do $n$-\'esimo m\^es.

 \item Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de maneiras de
       colocar id\^{e}nticos Toyotas, Cadillacs e Mercedes em um espa\c{c}o cujo
       tamanho \'{e} $n$ ``unidades'', sabendo que Mercedes e Cadillacs ocupam
       2 unidades cada um, e que Toyotas ocupam uma unidade cada um.

 \item Considere $n$ quadrados dispostos lado a lado, como mostra a figura:
       \begin{center} 
       \begin{picture}(175,25)
        \put(50,0){\line(1,0){30}}
        \put(50,15){\line(1,0){30}}
        \put(50,0){\line(0,1){15}}
        \put(65,0){\line(0,1){15}}
        \put(80,0){\line(0,1){15}}
        \put(95,8){\makebox(0,0){$\cdots$}}
        \put(110,0){\line(1,0){15}}
        \put(110,15){\line(1,0){15}}
        \put(110,0){\line(0,1){15}}
        \put(125,0){\line(0,1){15}}
        \put(57,17){\makebox(0,0)[b]{$1$}}
        \put(72,17){\makebox(0,0)[b]{$2$}}
        \put(117,17){\makebox(0,0)[b]{$n$}}
       \end{picture}
       \end{center}
       Seja $a_n = $ {\it n\'{u}mero de maneiras de colorir os quadrados, de forma
       que n\~{a}o fiquem dois quadrados vermelhos adjacentes\/}. Encontre uma
       rela\c{c}\~{a}o de recorr\^{e}ncia para $a_n$, para cada um dos seguintes casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada quadrado pode ser colorido de vermelho ou de verde.
        \item Cada quadrado pode ser colorido de vermelho, de verde, ou de
              amarelo.
        \item Generalize para $k$ cores (incluindo vermelho).
       \end{list}

 \item Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de maneiras
       de subir $n$ degraus, se em cada est\'{a}gio pudermos avan\c{c}ar 1, 3 ou 5
       degraus de uma vez.

 \item Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de
       sequ\^{e}ncias quatern\'{a}rias de $n$ d\'{\i}gitos
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item sem 1's consecutivos.
        \item com n\'{u}mero par de 0's.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que uma moeda seja lan\c{c}ada at\'{e} que apare\c{c}am 2 caras,
              quando ent\~{a}o o experimento termina. Encontre uma rela\c{c}\~{a}o de
              recorr\^{e}ncia para o n\'{u}mero de experimentos que terminam no
              $n$-\'{e}simo lan\c{c}amento ou antes.
        \item O mesmo, supondo que o experimento termina apenas quando aparece a
              terceira cara.
        \item Generalize para $k$ caras.
       \end{list}

 \item Sejam $n$ caixas distintas dispostas em uma fila. Encontre uma rela\c{c}\~{a}o
       de recorr\^{e}ncia para o n\'{u}mero de maneiras de distribuir $k$ bolas
       id\^{e}nticas de forma que cada caixa receba no m\'{a}ximo 1 bola, e que n\~{a}o
       haja caixas consecutivas com bolas.

 \item Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de sequ\^{e}ncias
       quatern\'{a}rias de $n$ d\'{\i}gitos com um n\'{u}mero (total) par de 1's e 2's.

 \item Encontre uma rela\c{c}\~{a}o de recorr\^{e}ncia para o n\'{u}mero de sequ\^{e}ncias
       bin\'{a}rias de $n$ d\'{\i}gitos com exatamente um par de 1's consecutivos.

 \item Mostre que $C_1(1+\sqrt{5})^n+C_2(1-\sqrt{5})^n$ \'{e} a solu\c{c}\~{a}o geral para
       $a_n-2a_{n-1}-4a_{n-2}=0$.

 \item Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=0$, $a_2=2$, $a_n+5a_{n-1}+6a_{n-2}=0$ para $n\geq 3$.
        \item $a_0=1$, $a_1=2$, $a_n-2a_{n-1}-a_{n-2}=0$ para $n\geq 2$.
       \end{list}

 \item Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=2$, $a_2=6$, $a_n-4a_{n-1}+4a_{n-2}=0$ para $n\geq 3$.
        \item $a_1=5$, $a_2=-5$, $a_n+6a_{n-1}+9a_{n-2}=0$ para $n\geq 3$.
       \end{list}

 \item Resolva a rela\c{c}\~{a}o de recorr\^{e}ncia
        $a_1=2$, $a_2=6$, $a_n-4a_{n-1}+4a_{n-2}=0$ para $n\geq 3$,
       usando fun\c{c}\~{a}o geradora. 

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

 \item Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_0=0$, $a_n+3a_{n-1}=2^n$ para $n\geq 1$.
        \item $a_1=0$, $a_2=0$, $a_n-4a_{n-1}+4a_{n-2}=(-2)^n$ para $n\geq 3$.
       \end{list}

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

 \item Resolva as seguintes rela\c{c}\~{o}es de recorr\^{e}ncia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=1$, $a_n^3=2a_{n-1}^3+1$ para $n\geq 2$. (Sugest\~{a}o: fa\c{c}a
              $b_n=a_n^3$.)
        \item $a_0=2$, $a_n=na_{n-1}+n!$ para $n\geq 1$.
       \end{list}

 \item Usando rela\c{c}\~{o}es de recorr\^{e}ncia, avalie as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1+2+\cdots+n$.
        \item $1+2+4+\cdots+2^n$.
        \item $1^2+2^2+\cdots+n^2$.
        \item $1\times 2+2\times 3+\cdots+n(n+1)$.
       \end{list}

\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}
