.Problema Olímpico: Sequências de A’s e B’s

Problema
(Indicado a partir do 2º ano do E. M.)

Considere as sequências formadas pelas letras A e B e definidas do seguinte modo:

todo conjunto de A’s consecutivos possui um número par de letras;
todo conjunto de B’s consecutivos possui um número ímpar de letras.

Exemplos de tais sequências são AA, B, AABBBAAAA, enquanto BBAAB e BBBBAAAAAB não são exemplos válidos, pois no início da primeira sequência há um número par de B’s consecutivos e, na segunda, um número ímpar de A’s no centro.
O “tamanho de cada sequência” é definido como a quantidade total de letras que a formam. Assim, por exemplo, ambas as sequências AABAA e AABBB têm tamanho $5$ .
Quantas dessas sequências de tamanho $14$ existem?

Para ajudar. . .

✐ Muitos exercícios envolvendo sequências podem ser resolvidos por algo que chamamos de relação de recorrência ou, simplesmente, recorrência.
Uma relação de recorrência é uma regra que, a menos de um número finito de termos iniciais, permite obter qualquer termo de uma determinada sequência em função dos seus antecessores imediatos na mesma sequência; neste caso, dizemos que a sequência foi definida recursivamente.

Solução

Vamos utilizar no problema a ideia de recursão, ou seja, vamos tentar encontrar ligações entre uma sequência de tamanho

$n$ e sequências de tamanhos menores. Sejam, então,

$a_n$ e

$b_n$ o número de sequências de tamanho

$n$ que terminam em A e B, respectivamente.
Vamos contar

$a_n$ e

$b_n$ separadamente.

$\color{#800000} (i)$ Iniciemos contando o número de sequências de tamanho

$n$ que terminam em A.

$\qquad \begin{array}{r |c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \textcolor{red}{\underline{ \, A \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &\textcolor{red}{n}\\ \end{array}$

Note que, se $n>2$ , para formarmos uma sequência de tamanho $n$ que termina em A, devemos necessariamente adicionar dois A’s no fim de uma sequência de tamanho $n-2$ .

$\qquad \begin{array}{r |c c c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \underline{ \, \, \, \, } & \textcolor{red}{\underline{ \, A \, }} & \textcolor{red}{\underline{ \, A \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &n-2&\textcolor{red}{n-1}&\textcolor{red}{n}\\ \end{array}$

No entanto, uma sequência de tamanho $n-2$ ou termina em B ou termina em A (neste caso, dois A’s), assim uma sequência de tamanho $n$ que termina em A tem uma das seguintes formas:

$\qquad \begin{array}{r |c c c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \underline{ \, B \, } & \textcolor{red}{\underline{ \, A \, }} & \textcolor{red}{\underline{ \, A \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &n-2&\textcolor{red}{n-1}&\textcolor{red}{n}\\ \end{array}$

$\qquad \begin{array}{r |c c c c c c c|} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \underline{ \, A \, } &\underline{ \, A \, } & \textcolor{red}{\underline{ \, A \, }} & \textcolor{red}{\underline{ \, A \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &n-3&n-2&\textcolor{red}{n-1}&\textcolor{red}{n}\\ \\ \end{array}$

Portanto, o número de sequências de comprimento $n$ que terminam em A é a soma entre o número de sequências de comprimento $n-2$ que terminam em A e o número de sequências de comprimento $n-2$ que terminam em B:

$\fcolorbox{black}{#B0C4DE}{$a_n = a_{n-2} + b_{n-2}$} \,$ .

$\color{#800000} (ii)$ Vamos agora contar o número de sequências de tamanho

$n$ que terminam em B.

$\qquad \begin{array}{r |c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \textcolor{red}{\underline{ \, B \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &\textcolor{red}{n}\\ \end{array}$

A princípio, uma sequência de tamanho $n$ que termine em B pode ser formada adicionando-se um B a uma sequência de tamanho $n-1$ , mas aqui precisamos de um certo cuidado.
Se a sequência de tamanho $n-1$ terminar em A, não há problema, pois acrescentaríamos um B (quantidade ímpar de letras) após um número par de letras A’s (pelo menos duas), conforme mostra o próximo esquema.

$\qquad \begin{array}{r |c c c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \underline{ \, A \, } & \underline{ \, A \, } & \textcolor{red}{\underline{ \, B \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &n-2&n-1&\textcolor{red}{n}\\ \end{array}$

Mas, ao acrescentarmos um B a uma sequência de tamanho $n-1$ que termina em B, estaríamos acrescentando uma letra B após um número ímpar de letras B’s, obtendo, assim, um número par de letras B’s e uma sequência inválida para nossos propósitos. Dessa forma, em vez de acrescentarmos um B a uma sequência de tamanho $n-1$ que termina em B, acrescentaremos dois B’s no final de uma sequência de tamanho $n-2$ que termina em B.

$\qquad \begin{array}{r |c c c c c c |} \text{letras} \, \rightarrow \, &\underline{ \, \, \, \, } & \underline{ \, \, \, \, } & \cdots & \underline{ \, B \, } & \textcolor{red}{\underline{ \, B \, }} & \textcolor{red}{\underline{ \, B \, }} \\ \text{ordem do termo} \, \rightarrow \, &1&2& \, \, &n-2&\textcolor{red}{n-1}&\textcolor{red}{n}\\ \end{array}$

Esse procedimento não acarreta o aparecimento de sequências inválidas, já que acrescentaremos dois B’s (quantidade par de letras) após um número ímpar de letras B’s consecutivas, obtendo uma quantidade ímpar de letras B’s consecutivas e definindo, então, uma sequência válida.
Assim, o número de sequências de comprimento $n$ que terminam em B é a soma entre o número de sequências de comprimento $n-1$ que terminam em A e o número de sequências de comprimento $n-2$ que terminam em B:

$\fcolorbox{black}{#B0C4DE}{$b_n = a_{n-1} + b_{n-2}$} \,$ .

Por $\color{#800000} (i)$ e $\color{#800000} (ii)$ , temos as recursões:
$\qquad \qquad a_n = a_{n-2} + b_{n-2}\\ \qquad \qquad b_n = a_{n-1} + b_{n-2}$
e podemos, finalmente, obter o número de sequências de tamanho $14$ que podem ser definidas conforme solicitado no problema.
Contando os casos iniciais, claramente observamos que:

$a_1 = 0$ , pois existe uma única sequência de comprimento $1$ que termina com a letra A: A, e esta não atende à restrição do problema;
$b_1 = 1$ , pois existe uma única sequência de comprimento $1$ que termina com a letra B: B, e esta atende à restrição do problema;
$a_2 = 1$ , pois existem duas sequências de comprimento $2$ que terminam com a letra A: AA e BA, e apenas a primeira atende à restrição do problema;
$b_2 = 0$ , pois existem duas sequências de comprimento $2$ que terminam com a letra B: AB e BB, e nenhuma atende à restrição do problema.

Com essas quatro informações e com as duas fórmulas de recorrência
$\qquad \qquad a_n = a_{n-2} + b_{n-2}\\ \qquad \qquad b_n = a_{n-1} + b_{n-2}$
podemos construir a tabela abaixo, que nos fornecerá a resposta do problema.

$\begin{array}{|r||r|r|r||r||r|r|} \hline n & a_n & b_n & & n & a_n & b_n\\ \hline 1&0&1& & 8&6&10\\ 2&1&0&& 9&11&11\\ 3&1&2& &10&16&21\\ 4&1&1&& 11&22&27\\ 5&3&3&& 12&37&43\\ 6&2&4&& 13&49&64\\ 7&6&5& &14&80&92\\ \hline \end{array}$

Portanto, o número total de sequências de tamanho $14$ será $\fcolorbox{black}{#eee0e5}{$a_{14} + b_{14} =172$}$ .

Solução elaborada pelos Moderadores do Blog.