\documentclass[12pt,a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\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{Exame Especial} \hfill 13/12/2013.

\vspace*{3mm}
\begin{enumerate}
% \item Prove por indução que, para todo $n\in \mbox{\bf N}$, $\sum_{k=0}^{n}(k2^k)=(n-1)2^{n+1}+2$.

 \item Uma sorveteria produz sorvetes de 10 sabores diferentes. Supondo que ela vá doar 100 sorvetes para as
       crianças de uma creche, quantos tipos de doações são possíveis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se a doação pode ser constituída de sorvetes de quaisquer sabores?
        \item Se a doação deve ser conter pelo menos 2 sorvetes de cada sabor?
       \end{list}

       \textit{Solu\c{c}\~ao}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $C(10-1+100,100)$.
        \item $C(10-1+80,80)$.
       \end{list}

 \item Utilizando funções geradoras, determine o número de soluções em inteiros para a equação:
       \begin{quote}
        $x_1+x_2+x_3+x_4\leq 10$, com $1\leq x_i\leq 10$.
       \end{quote}

       \textit{Solu\c{c}\~ao}:
       
        Fun\c c\~ao geradora: $(x+x^2+\cdots+x^{10})^4(1+x+x^2+\cdots)=x^4(1+x+x^2+\cdots+x^9)^4(1+x+x^2+\cdots)
				=x^4(1-x^{10})^4(1+x+x^2+\cdots)^5=x^4[C(4,0)-C(4,1)x^{10}+C(4,2)x^{20}-C(4,3)x^{30}+C(4,4)x^{40}]
				[C(5-1+0,0)+C(5-1+1,1)x+C(5-1+2,2)x^2+\cdots)]$.
            
				Coeficiente de $x^{10}$: $C(4,0)C(5-1+6,6)=C(10,6)=210$.

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

       {\it Solução\/}:

       Equação característica: $x^2+5x+6=0$. As raízes são $x_1=-2$, $x_2=-3$. Logo a solução geral é
			 $C_1(-2)^n+C_2(-3)^n$. Para satisfazer as condições iniciais deve-se ter $C_1(-2)^1+C_2(-3)^1=0$
			 e $C_1(-2)^2+C_2(-3)^2=2$, ou seja:
       \begin{enumerate}
        \item[\ ] $-2C_1-3C_2=0$
        \item[\ ] $4C_1+9C_2=2$
       \end{enumerate}
       Resolvendo esse sistema, obtém-se $C_1=-1$ e $C_2=2/3$. Logo, a solução da RR é $a_n=(-1)(-2)^n+(2/3)(-3)^n
			 =(-2)^{n+1}+(2/3)(-3)^n$.

 \item Encontre o número de sequências de $n$ dígitos decimais (0 a 9) em que cada dígito apareça pelo
       menos uma vez na sequência.

       \textit{Solução}:

       Seja $U$ o conjunto de todas as sequências de $n$ dígitos decimais. Seja $S_i$ o conjunto das sequências de
			 $n$ elementos em que o dígito $i$ aparece pelo menos uma vez. Pede-se $N(S_0\cap S_1\cap \ldots\cap S_9)$,
			 que é igual a $N(U)-N(\overline{S_0}\cup\overline{S_1}\cup \ldots\cup \overline{S_9})$. Como:
       \begin{itemize}
        \item $N(U)=10^n$;
        \item $N(\overline{S_i})=9^n$;
        \item $N(\overline{S_i}\cap\overline{S_j})=8^n$ para $j\not=i$;
        \item etc.
       \end{itemize}
       tem-se:
       \[N(S_0\cap S_1\cap \ldots\cap S_9)=10^n-\left[{10\choose 1}9^n-{10\choose 2}8^n+\cdots+(-1)^{10}{10\choose 10}
			   (10-10)^n\right]\mbox{.}\]
       Logo, $N(S_0\cap S_1\cap \ldots\cap S_9)=\sum_{i=0}^{10}(-1)^iC(10,i)(10-i)^n$.

 \item Qual é o maior número possível de arestas em um grafo com 31 vértices, se cada vértice tem grau, no máximo, igual a 3?

       \textit{Solução}:

       Sabe-se que $\sum_{v\in V}\mbox{\it grau\/}(v)=2|E|$. Como o número de vértices de grau ímpar é par, para satisfazer
			 as condiç\~oes do problema, basta ter $\sum_{v\in V}\mbox{\it grau\/}(v)=30\times 3+2=92$. Assim, o número máximo de
			 arestas é $|E|=92/2=46$.

% \item Para que valores de $m$ e $n$ são $K_n$ e $K_{m,n}$ Eulerianos?

%       \textit{Solução}:

%       $K_n$ é Euleriano quando $n$ é ímpar, pois, neste caso, todos os seus vértices têm grau par. $K_{m,n}$ é Euleriano
%			 quando $m$ e $n$ são pares.

\end{enumerate}

\end{document}

