\documentclass[11pt,a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\usepackage{comment}

\newcounter{conta}

\begin{document}
 
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
{\it Matemática Discreta} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \hfill www.dcc.ufmg.br/\verb+~+nvieira\\
\underline{Terceira Lista de Exercícios} \hfill Entrega: 30/10/2013

\vspace*{2mm}
\noindent {\bf Relações de Recorrência}
 
\vspace*{2mm}

\begin{enumerate}
 \item Um banco paga 4,5\% de juros por ano. Além disso, ele paga um bônus de \$100 reais no final de
       cada ano (após pagos os juros). Encontre uma relação de recorrência para o total pago após $n$ anos, se o
			 investimento inicial for de \$200 reais.

 \item Encontre uma relação de recorrência para o número de sequências quaternárias de $n$ dígitos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item sem 1's consecutivos.
        \item com número par de 0's.
       \end{list}
       %Townsend 4.1/10

 \item Encontre uma relação de recorrência para o número de maneiras de colocar idênticos Toyotas,
       Cadillacs e Mercedes em um espaço cujo tamanho é $n$ ``unidades'', sabendo que Mercedes e Cadillacs ocupam
       2 unidades cada um, e que Toyotas ocupam uma unidade cada um.
       %Townsend 4.1/11
       
 \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úmero de maneiras de colorir os quadrados, de forma que não fiquem dois quadrados vermelhos
			 adjacentes\/}. Encontre uma relação de recorrê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ção de recorrência para o número de maneiras de subir $n$ degraus, se em
       cada estágio pudermos avançar 1, 3 ou 5 degraus de uma vez.
       %Townsend 4.1/12

 \item Seja o conjunto de dígitos e letras $X=\{1,2,3,4,a,b,c,d,e,f,g\}$. Encontre uma relação de
       recorrência para o número de sequências de $n$ símbolos de $X$, para cada uma das seguintes
			 situações:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item não há letras consecutivas (idênticas ou não).
        \item não há dígito seguido de letra.
        \item o número de letras é par.
       \end{list}

 \item Encontre uma relação de recorrência para o número de sequências ternárias de $n$ dígitos sem a
       subsequência 012.
%      EX. 7, pag. 283. Tucker

 \item Encontre uma relação de recorrência para o número de regiões criadas por $n$ linhas sobre uma folha
       de papel se $k$ das linhas são paralelas e cada uma das outras $n-k$ intersepta todas as linhas (e não mais de 2
			 linhas se interseptam em um único ponto).
%      Ex. 13(a), pag. 289. Tucker

\begin{comment}
 \item Encontre uma relação de recorrência para o número de sequências de $r$ elementos tomados de um
       conjunto de $n$ elementos.
       %Townsend 4.1/20

 \item Encontre uma relação de recorrência para o número de multiconjuntos de $r$ elementos tomados de um
       conjunto de $n$ elementos.
       %Townsend 4.1/20

 \item Encontre uma relação de recorrência para o número de decomposições de um conjunto de $n$
       elementos em exatamente $k$ partes (conjuntos não vazios disjuntos).
       %Townsend 4.1/23

 \item Sejam $n$ caixas distintas dispostas em uma fila. Encontre uma relação de recorrência para o
       número de maneiras de distribuir $k$ bolas idênticas de forma que cada caixa receba no máximo 1 bola, e que não
       haja caixas consecutivas com bolas.
       %Townsend 4.1/24
\end{comment}

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

 \item Resolva as seguintes relações de recorrê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$.
        \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 as seguintes relações de recorrê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$.
        \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$.
        \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ções de recorrência:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $a_1=1$, $a_n^3=2a_{n-1}^3+1$ para $n\geq 2$. (Sugestão: faç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ções de recorrência, avalie as seguintes somas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \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}
\end{enumerate}

\vspace*{2mm}
\noindent {\bf Princípio de inclusão e exclusão}
 
\vspace*{2mm}
\begin{enumerate}
 \item Numa cidade em que são publicados os jornais A, B e C, foram obtidos os seguintes resultados
       numa pesquisa: 20\% da população lê o jornal A, 16\% o jornal B, 14\% o jornal C; 8\% lê A e B, 5\% A e C e 4\% B
       e C. Somente 2\% lê os três jornais. Qual a porcentagem da população que não lê nenhum destes três jornais?
        
 \item Dentre os números de 1 a 1000, inclusive, quantos são divisíveis por 2, 5 ou 12? Quantos não
       são divisíveis por 5, nem por 6, nem por 8?

 \item Encontre o número de sequê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ência.

 \item Quantos arranjos existem das letras A,A,A,B,B,B,C,C,C, nos quais não
       apareçam 3 letras consecutivas idênticas?

 \item Usando o princípio da inclusão e exclusão, determine o número de
       soluções inteiras para $x_1+x_2+x_3+x_4=20$, se $-2\leq x_k\leq 10$.

 \item Uma companhia de sabão em p\'{o} oferece 3 tipos diferentes de cupons em suas caixas de sabão.
       Cada caixa contém um cupom; se você colecionar pelo menos um de cada tipo, voce ganha um brinde. Qual é a
			 probabilidade de você ganhar um brinde, se você comprar 10 caixas? (A probabilidade é o número de distribuições
			 possíveis em que aparece pelos um cupom de cada tipo, dividido pelo número total de distribuições possíveis.)

 \item Oito pessoas entram em um elevador, no primeiro andar. O elevador descarrega passageiros em cada
       um dos andares seguintes (no mínimo, um passageiro por andar), até ficar vazio no quinto andar (após descarregar, no
       mínimo, um passageiro). Determine, usando o princípio da inclusão e exclusão, de quantas maneiras diferentes isto
			 pode acontecer.

 \item Em quantas permutações de 1,2,\ldots, $n$, um número $k$ nunca é imediatamente seguido de $k+1$?

 \item Quantas maneiras existem de arranjar as letras em REDIVIDERS de forma que apareça pelo menos
       um par de letras consecutivas idênticas?

 \item De quantas maneiras podemos permutar os dígitos 1, 2, 3, 4, 5, 6, 7, 8, 9
       de forma que nenhum dígito par fique em sua posição natural?
\end{enumerate}

\end{document}