\documentclass[11pt,a4paper]{article}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}

\pagestyle{empty}
\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 \\
\underline{Terceira Prova} \hfill 30/10/2013

\vspace*{3mm}
\noindent As 5 primeiras questões valem 3 pontos,  e as últimas 3 questões valem 1 ponto cada uma.
\vspace*{2mm}
\begin{enumerate}
 \item \label{q1} {\footnotesize Um certo banco paga 6\% de juros ao ano para um certo tipo de aplicação. Além disso, ele 
       paga um bônus de 10\% do investimento inicial ao final de cada ano (após computados os juros). Encontre uma relação 
			 de recorrência para o saldo após decorridos $n$ anos, se não houver nenhum saque, e se o investimento inicial for de
			 R\$ $k$.}

       \textit{Solução}:
 
       $S_0=k$, \\
	     $S_n=1,06S_{n-1}+0,10k$ para $n\geq 1$.

 \item {\footnotesize Seja $a_n$ o número de maneiras de dispor $n$ bandeirinhas lado a lado, podendo cada bandei\-ri\-nha 
       ser de uma das cores: verde, amarelo ou azul. Determine uma relação de recorrência para $a_n$, supondo que
			 \emph{bandeirinhas adjacentes não podem ser ambas amarelas}.}

       \textit{Solução}:

       $a_0=1$, $a_1=3$; \\
			 $a_n= 2a_{n-1}+2a_{n-2}$ para $n\geq 2$.
			
			 Veja: o primeiro termo conta as sequências em que a última banderinha é verde ou azul; o segundo conta as
			 sequências em que a última é amarela e, com isto, a penúltima é verde ou azul.

 \item \label{q5} {\footnotesize Resolva a relação de recorrência:
       \begin{quote}
			   $a_0=0$, $a_1=3$; \\
			   $a_n= a_{n-1}+2a_{n-2}$ para $n\geq 2$.
			 \end{quote}}

       \textit{Solução}:

       Equação característica: $\alpha^2-\alpha-2=0$. Suas raízes são $\alpha_1=-1$ e $\alpha_2=2$. Logo, a solução geral
			 para a parte recorrente é: $C_1(-1)^n+C_22^n$.
			
			 Para as condições iniciais tem-se $C_1(-1)^0+C_22^0=0$ e $C_1(-1)^1+C_22^1=3$, de onde se segue que $C_1=-1$ e $C_2=1$.
			 Portanto, $a_n=(-1).(-1)^n+1.2^n=2^n+(-1)^{n+1}$.

 \item {\footnotesize Resolva a relação de recorrência:
       \begin{quote}
			   $a_0=0$, $a_1=3$; \\
			   $a_n= a_{n-1}+2a_{n-2} + 4.3^n$ para $n\geq 2$.
			 \end{quote}}

       \textit{Solução}:

       A solução geral para a parte homogênea é (da questão \ref{q5}): $g(n)=C_1(-1)^n+C_22^n$.
			
			 A solução para a parte não homogênea é da forma $A3^n$. Assim, $A3^n-A3^{n-1}-2A3^{n-2}=4.3^n$.
			 Segue-se que $A=9$ e $p(n)=3^{n+2}$.
			
			 Logo, a solução geral para a parte recorrente é $g(n)+p(n)=C_1(-1)^n+C_22^n+3^{n+2}$. Para as condições iniciais:
			 $C_1(-1)^0+C_22^0+3^{n+2}=0$ e $C_1(-1)^1+C_22^1+3^{n+2}=3$. Tem-se, então, que $C_1=2$ e $C_2=-11$.			
			 Portanto, $a_n=3^{n+2}-11.2^n+2(-1)^n$.

 \item {\footnotesize De quantas maneiras podemos permutar os 10 dígitos decimais de forma que nenhum dígito ímpar fique em 
       sua posição natural? Considere que a posição natural de 0 é 0, a posição natural de 1 é 1, a posição natural de 2 é 2,
			 e assim por diante. Por exemplo, o arranjo 0563912748 só tem em suas posições naturais os dígitos 0, 3 e 7.}

       \textit{Solução}:

       Seja $A_i$ o conjunto dos arranjos em que o dígito ímpar $i$ aparece em sua posição natural.
       Pede-se, então, $N(\overline{A_1}\cap\overline{A_3}\cap\overline{A_5}\cap\overline{A_7}\cap\overline{A_9})$
       Tem-se:

       \[N(\overline{A_1}\cap\overline{A_3}\cap\overline{A_5}\cap\overline{A_7}\cap\overline{A_9})=10!-
         \left[{5\choose 1}9!-{5\choose 2}8!+{5\choose 3}7!-{5\choose 4}6!+{5\choose 5}5!\right]\mbox{.}\]

\end{enumerate}

\begin{enumerate}
 \item[6.] Seja novamente $a_n$ o número de maneiras de dispor $n$ bandeirinhas lado a lado, podendo cada
       bandeirinha ser de uma das cores: verde, amarelo ou azul. Determine uma relação de recorrência para $a_n$,
			 supondo agora que \emph{bandeirinhas adjacentes não podem ter a mesma cor}.

       \textit{Solução}:

       $a_0=1$, $a_1=3$; \\
			 $a_n= 2a_{n-1}$ para $n\geq 2$.
			
			 Veja: a $n$-ésima cor é uma das \textbf{duas} diferentes da $n-1$-ésima. \textbf{Mas},
			 isto só vale se $n\geq 2$ (ou seja, existe cor anterior); logo, é preciso dizer que $a_1=3$ explicitamente.

 \item[7.] Resolva a relação de recorrência obtida na questão \ref{q1}.

       \textit{Solução}:

       A solução para a parte homogênea é $g(n)=C_1(1,06)^n$.
				
		   A solução para a parte não homogênea é um polinômio de grau zero, $A$. Substituindo na parte recorrente:
	     $A-1,06A=0,1k$. Logo, $A=-0,1k/0,06=-5k/3$. Logo, a solução da parte não homogênea é $p(n)=-5k/3$.
		
			 Portanto, a solução geral da parte recorrente é $g(n)+p(n)=C_1(1,06)^n-5k/3$.
							
			 Como $S_0=k$, $C_1(1,06)^0-5k/3=k$ e, portanto, $C_1=8k/3$. Logo, $S_n=8(1,06)^nk/3-5k/3=[8(1,06)^n-5]k/3$.

 \item[8.] Quantos arranjos existem das letras AAAOOOXX em que não apareçam 3 letras conse\-cu\-tivas idênticas?

       \textit{Solução}:

       Sejam $A$ o conjunto dos arranjos em que aparecem 3 As consecutivos e $O$ o conjunto dos arranjos
       em que aparecem 3 Os consecutivos. 

       Então, $N(\overline{A}\cap\overline{O})=N(U)-N(A\cup O)$. Logo,
       \[N(\overline{A}\cap\overline{O})=P(8;3,3,2)-\left[{2 \choose 1}P(6;3,2,1)-{2 \choose 2}P(4;2,1,1)\right]\mbox{.}\]
       Portanto,
       \[N(\overline{A}\cap\overline{O})=\frac{8!}{6.6.2}-\left[2\frac{6!}{6.2}-\frac{4!}{2}\right]=560-120+12=452\mbox{.}\]
\end{enumerate}

\end{document}
 