Problema Exemplos de tais sequ\u00eancias s\u00e3o AA<\/strong>, B<\/strong>, AABBBAAAA<\/strong>, enquanto BBAAB <\/strong> e BBBBAAAAAB <\/strong> n\u00e3o s\u00e3o exemplos v\u00e1lidos, pois no in\u00edcio da primeira sequ\u00eancia h\u00e1 um n\u00famero par de B’s consecutivos e, na segunda, um n\u00famero \u00edmpar de A’s no centro. \n<\/div>\n \n Para ajudar. . . <\/p>\n \n ✐ <\/span> Muitos exerc\u00edcios envolvendo sequ\u00eancias podem ser resolvidos por algo que chamamos de rela\u00e7\u00e3o de recorr\u00eancia<\/strong><\/span> ou, simplesmente, recorr\u00eancia<\/strong><\/span>. \n Solu\u00e7\u00e3o<\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c |} \n Note que, se [tex]n>2[\/tex], para formarmos uma sequ\u00eancia de tamanho [tex]n[\/tex] que termina em A, devemos necessariamente adicionar dois A’s no fim de uma sequ\u00eancia de tamanho [tex]n-2[\/tex].<\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c c c |} \n No entanto, uma sequ\u00eancia de tamanho [tex]n-2[\/tex] ou termina em B ou termina em A (neste caso, dois A’s), assim uma sequ\u00eancia de tamanho [tex]n[\/tex] que termina em A tem uma das seguintes formas:<\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c c c |} \n ou <\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c c c c|} \n Portanto, o n\u00famero de sequ\u00eancias de comprimento [tex]n[\/tex] que terminam em A \u00e9 a soma entre o n\u00famero de sequ\u00eancias de comprimento [tex]n-2[\/tex] que terminam em A e o n\u00famero de sequ\u00eancias de comprimento [tex]n-2[\/tex] que terminam em B:<\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c |} \n A princ\u00edpio, uma sequ\u00eancia de tamanho [tex]n[\/tex] que termine em B pode ser formada adicionando-se um B a uma sequ\u00eancia de tamanho [tex]n-1[\/tex], mas aqui precisamos de um certo cuidado. \n [tex]\\qquad \\begin{array}{r |c c c c c c |} \n Mas, ao acrescentarmos um B a uma sequ\u00eancia de tamanho [tex]n-1[\/tex] que termina em B, estar\u00edamos acrescentando uma letra B ap\u00f3s um n\u00famero \u00edmpar de letras B’s, obtendo, assim, um n\u00famero par de letras B’s e uma sequ\u00eancia inv\u00e1lida para nossos prop\u00f3sitos. Dessa forma, em vez de acrescentarmos um B a uma sequ\u00eancia de tamanho [tex]n-1[\/tex] que termina em B, acrescentaremos dois B’s no final de uma sequ\u00eancia de tamanho [tex]n-2[\/tex] que termina em B. <\/p>\n \n [tex]\\qquad \\begin{array}{r |c c c c c c |} \n Esse procedimento n\u00e3o acarreta o aparecimento de sequ\u00eancias inv\u00e1lidas, j\u00e1 que acrescentaremos dois B’s (quantidade par de letras) ap\u00f3s um n\u00famero \u00edmpar de letras B’s consecutivas, obtendo uma quantidade \u00edmpar de letras B’s consecutivas e definindo, ent\u00e3o, uma sequ\u00eancia v\u00e1lida. Por [tex]\\color{#800000} (i)[\/tex] e [tex]\\color{#800000} (ii)[\/tex], temos as recurs\u00f5es: Com essas quatro informa\u00e7\u00f5es e com as duas f\u00f3rmulas de recorr\u00eancia [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]<\/p>\n Portanto, o n\u00famero total de sequ\u00eancias de tamanho [tex]14[\/tex] ser\u00e1 [tex]\\fcolorbox{black}{#eee0e5}{$a_{14} + b_{14} =172$}[\/tex].<\/p>\n Solu\u00e7\u00e3o elaborada pelos Moderadores do Blog<\/strong>.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Problema (Indicado a partir do 2\u00ba ano do E. M.) Considere as sequ\u00eancias formadas pelas letras A e B e definidas do seguinte modo: todo conjunto de A’s consecutivos possui um n\u00famero par de letras; todo conjunto de B’s consecutivos possui um n\u00famero \u00edmpar de letras. Exemplos de tais sequ\u00eancias s\u00e3o AA, B, AABBBAAAA, enquanto … <\/p>\n
\n (Indicado a partir do 2\u00ba ano do E. M.)<\/span><\/p>\n
\nConsidere as sequ\u00eancias formadas pelas letras A e B e definidas do seguinte modo:<\/p>\n\n
\nO “tamanho de cada sequ\u00eancia” \u00e9 definido como a quantidade total de letras que a formam. Assim, por exemplo, ambas as sequ\u00eancias AABAA e AABBB t\u00eam tamanho [tex]5[\/tex].
\nQuantas dessas sequ\u00eancias de tamanho [tex]14[\/tex] existem?<\/strong><\/p>\n![\"\"](\"http:\/\/clubes.obmep.org.br\/blog\/wp-content\/uploads\/2013\/01\/menino.jpg\")
<\/p>\n
\nUma rela\u00e7\u00e3o de recorr\u00eancia \u00e9 uma regra que, a menos de um n\u00famero finito de termos iniciais, permite obter qualquer termo de uma determinada sequ\u00eancia em fun\u00e7\u00e3o dos seus antecessores imediatos na mesma sequ\u00eancia; neste caso, dizemos que a sequ\u00eancia foi definida recursivamente.\n<\/div>\n
\nVamos utilizar no problema a ideia de recurs\u00e3o, ou seja, vamos tentar encontrar liga\u00e7\u00f5es entre uma sequ\u00eancia de tamanho [tex]n[\/tex] e sequ\u00eancias de tamanhos menores. Sejam, ent\u00e3o, [tex]a_n[\/tex] e [tex]b_n[\/tex] o n\u00famero de sequ\u00eancias de tamanho [tex]n[\/tex] que terminam em A e B, respectivamente.
\nVamos contar [tex]a_n[\/tex] e [tex]b_n[\/tex] separadamente. <\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\textcolor{red}{\\underline{ \\, A \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\underline{ \\, \\, \\, \\, } & \\textcolor{red}{\\underline{ \\, A \\, }} & \\textcolor{red}{\\underline{ \\, A \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &n-2&\\textcolor{red}{n-1}&\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\underline{ \\, B \\, } & \\textcolor{red}{\\underline{ \\, A \\, }} & \\textcolor{red}{\\underline{ \\, A \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &n-2&\\textcolor{red}{n-1}&\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\underline{ \\, A \\, } &\\underline{ \\, A \\, } & \\textcolor{red}{\\underline{ \\, A \\, }} & \\textcolor{red}{\\underline{ \\, A \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &n-3&n-2&\\textcolor{red}{n-1}&\\textcolor{red}{n}\\\\
\n\\\\
\n\\end{array}[\/tex]<\/p>\n\n
\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\textcolor{red}{\\underline{ \\, B \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\nSe a sequ\u00eancia de tamanho [tex]n-1[\/tex] terminar em A, n\u00e3o h\u00e1 problema, pois acrescentar\u00edamos um B (quantidade \u00edmpar de letras) ap\u00f3s um n\u00famero par de letras A’s (pelo menos duas), conforme mostra o pr\u00f3ximo esquema.<\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\underline{ \\, A \\, } & \\underline{ \\, A \\, } & \\textcolor{red}{\\underline{ \\, B \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &n-2&n-1&\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\n\\text{letras} \\, \\rightarrow \\, &\\underline{ \\, \\, \\, \\, } & \\underline{ \\, \\, \\, \\, } & \\cdots & \\underline{ \\, B \\, } & \\textcolor{red}{\\underline{ \\, B \\, }} & \\textcolor{red}{\\underline{ \\, B \\, }} \\\\
\n\\text{ordem do termo} \\, \\rightarrow \\, &1&2& \\, \\, &n-2&\\textcolor{red}{n-1}&\\textcolor{red}{n}\\\\
\n\\end{array}[\/tex]<\/p>\n
\nAssim, o n\u00famero de sequ\u00eancias de comprimento [tex]n[\/tex] que terminam em B \u00e9 a soma entre o n\u00famero de sequ\u00eancias de comprimento [tex]n-1[\/tex] que terminam em A e o n\u00famero de sequ\u00eancias de comprimento [tex]n-2[\/tex] que terminam em B:<\/p>\n\n
\n
\n [tex]\\qquad \\qquad a_n = a_{n-2} + b_{n-2}\\\\
\n\\qquad \\qquad b_n = a_{n-1} + b_{n-2}[\/tex]
\ne podemos, finalmente, obter o n\u00famero de sequ\u00eancias de tamanho [tex]14[\/tex] que podem ser definidas conforme solicitado no problema.
\nContando os casos iniciais, claramente observamos que:<\/p>\n\n
\n[tex]\\qquad \\qquad a_n = a_{n-2} + b_{n-2}\\\\
\n\\qquad \\qquad b_n = a_{n-1} + b_{n-2}[\/tex]
\n podemos construir a tabela abaixo, que nos fornecer\u00e1 a resposta do problema.<\/p>\n
\n