\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent {\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG\\
\underline{Terceira Prova}/Solu\c{c}\~ao do professor \hfill 02/06/2008

\begin{enumerate}
 \item {\footnotesize Uma pessoa deve pintar uma seq\"u\^encia de $n$ blocos, $n\geq 1$,  com as cores vermelha,
       azul e branca, cada bloco com uma \'unica cor. Encontre uma rela\c{c}\~ao de recorr\^encia
       para o n\'umero de seq\"u\^encias poss\'{\i}veis em cada um dos seguintes casos:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item N\~ao h\'a restri\c{c}\~ao.
        \item Blocos consecutivos n\~ao podem receber a mesma cor.
        \item Blocos consecutivos n\~ao podem ser pintados de branco.
        \item O n\'umero de blocos pintados de branco deve ser par.
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:

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

 \item {\footnotesize Encontre solu\c{c}\~oes gerais para
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item a parte homog\^enea, e
        \item a parte recorrente
       \end{list}
       da rela\c{c}\~ao de recorr\^encia:
       \begin{quote}
        $a_0=1$, $a_1=2$;
        $a_n=5a_{n-1}-6a_{n-2}+3n+2$ para $n\geq 2$.
       \end{quote}}

       \textit{Solu\c{c}\~ao\/}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Resolvendo-se a equa\c{c}\~ao caracter\'{\i}stica $x^2-5x+6=0$, obt\'em-se:
              $x_1=3$ e $x_2=2$. Logo, a solu\c{c}\~ao geral para a parte homog\^enea
              \'e $g(n)=C_13^n+C_22^n$.
        \item Uma solu\c{c}\~ao particular para a parte recorrente tem a forma $An+B$. Fazendo-se
              a substitui\c{c}\~ao, obt\'em-se a equa\c{c}\~ao $(An+B)-5A(n-1)-5B+6A(n-2)+6B=3n+2$.
              Desta, obt\'em-se $2An-7A+B=3n+2$, de onde se tira que $A=3/2$ e $B=25/4$. Portanto,
              a solu\c{c}\~ao particular \'e $p(n)=(3n/2)+(25/4)$. E a solu\c{c}\~ao geral para a
              parte recorrente \'e $g(n)+p(n)=C_13^n+C_22^n+(3n/2)+(25/4)$.
       \end{list}

 \item {\footnotesize Solucione a rela\c{c}\~ao de recorr\^encia:
       \begin{quote}
        $a_0=-1$;
        $a_n=n(a_{n-1}+1)$ para $n\geq 1$.
       \end{quote}}

       \textit{Solu\c{c}\~ao\/}:

       A solu\c{c}\~ao para $u_0=1$, $u_n=nu_{n-1}$ para $n\geq 1$, \'e $u_n=n!$. E a solu\c{c}\~ao
       para $v_0=-1$, $v_n=v_{n-1}+1/(n-1)!$ \'e $v_n=-1+\sum_{k=0}^{n-1}1/k!=$. Logo,
       \[a_n=u_nv_n=n!(-1+\sum_{k=0}^{n-1}1/k!)=(n!\sum_{k=0}^{n}1/k!) -(n!+1)\mbox{.}\]

 \item {\footnotesize Uma certa crian\c{c}a tem como tarefa comer 6 bolas de sorvete de tr\^es sabores diferentes:
       duas bolas de abacaxi, duas de chocolate e duas de morango. Sabendo que ela deve comer
       uma bola (toda) de cada vez e que n\~ao pode comer duas bolas de mesmo sabor consecutivamente,
       de quantas maneiras ela pode cumprir a tarefa?}

       \textit{Solu\c{c}\~ao\/}:

       Seja $A$ o conjunto de tarefas com bolas de abacaxi n\~ao consecutivas, $C$ o conjunto com bolas
       de chocalate n\~ao consecutivas e $M$ o conjunto com bolas de morango n\~ao consecutivas. A
       solu\c{c}\~ao \'e $N(A\cap C\cap M)$, ou seja, $N(U)-N(\overline{A}\cap \overline{C}\cap \overline{M})$,
       que \'e igual a:
        \[\frac{6!}{2!2!2!}-({3 \choose 1}\frac{5!}{2!2!}-{3 \choose 2}\frac{4!}{2!}+{3 \choose 3}3!)=
          \frac{720}{8}-3\frac{120}{4}+3\frac{24}{2}-6=30\mbox{.}\]
\end{enumerate}

\end{document}
