.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 [tex]5[/tex].
Quantas dessas sequências de tamanho [tex]14[/tex] 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 [tex]n[/tex] e sequências de tamanhos menores. Sejam, então, [tex]a_n[/tex] e [tex]b_n[/tex] o número de sequências de tamanho [tex]n[/tex] que terminam em A e B, respectivamente.
Vamos contar [tex]a_n[/tex] e [tex]b_n[/tex] separadamente.

[tex]\color{#800000} (i)[/tex] Iniciemos contando o número de sequências de tamanho [tex]n[/tex] que terminam em A.

[tex]\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}[/tex]

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

[tex]\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}[/tex]

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

[tex]\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}[/tex]

ou

[tex]\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}[/tex]

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

    • [tex]\fcolorbox{black}{#B0C4DE}{$a_n = a_{n-2} + b_{n-2}$} \, [/tex].
[tex]\color{#800000} (ii)[/tex] Vamos agora contar o número de sequências de tamanho [tex]n[/tex] que terminam em B.

[tex]\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}[/tex]

A princípio, uma sequência de tamanho [tex]n[/tex] que termine em B pode ser formada adicionando-se um B a uma sequência de tamanho [tex]n-1[/tex], mas aqui precisamos de um certo cuidado.
Se a sequência de tamanho [tex]n-1[/tex] 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.

[tex]\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}[/tex]

Mas, ao acrescentarmos um B a uma sequência de tamanho [tex]n-1[/tex] 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 [tex]n-1[/tex] que termina em B, acrescentaremos dois B’s no final de uma sequência de tamanho [tex]n-2[/tex] que termina em B.

[tex]\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}[/tex]

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 [tex]n[/tex] que terminam em B é a soma entre o número de sequências de comprimento [tex]n-1[/tex] que terminam em A e o número de sequências de comprimento [tex]n-2[/tex] que terminam em B:

    • [tex]\fcolorbox{black}{#B0C4DE}{$b_n = a_{n-1} + b_{n-2}$} \, [/tex].

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

  • [tex]a_1 = 0[/tex], pois existe uma única sequência de comprimento [tex]1[/tex] que termina com a letra A: A, e esta não atende à restrição do problema;
  • [tex]b_1 = 1[/tex], pois existe uma única sequência de comprimento [tex]1[/tex] que termina com a letra B: B, e esta atende à restrição do problema;
  • [tex]a_2 = 1[/tex], pois existem duas sequências de comprimento [tex]2[/tex] que terminam com a letra A: AA e BA, e apenas a primeira atende à restrição do problema;
  • [tex]b_2 = 0[/tex], pois existem duas sequências de comprimento [tex]2[/tex] 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
[tex]\qquad \qquad a_n = a_{n-2} + b_{n-2}\\
\qquad \qquad b_n = a_{n-1} + b_{n-2}[/tex]
podemos construir a tabela abaixo, que nos fornecerá a resposta do problema.

[tex]\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}[/tex]

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


Solução elaborada pelos Moderadores do Blog.

Link permanente para este artigo: http://clubes.obmep.org.br/blog/problema-olimpico-sequencias-de-as-e-bs/