Questão 2 olimpíada matemática 2011 fase 2 nível 3
Começando com qualquer número natural não nulo é sempre possível formar uma sequência de números que termina em 1, seguindo repetidamente as instruções abaixo:
• se o número for ímpar, soma-se 1;
• se o número for par, divide-se por 2.
Por exemplo, começando com o número 21, forma-se a seguinte sequência:
21→22→11→12→6→3→4→2→1
Nessa sequência aparecem nove números; por isso, dizemos que ela tem comprimento 9. Além disso, como ela começa com um número ímpar, dizemos que ela é uma sequência ímpar.
a) Escreva a sequência que começa com 37.
b) Existem três sequências de comprimento 5, sendo duas pares e uma ímpar. Escreva essas sequências.
c) Quantas são as sequências pares e quantas são as sequências ímpares de comprimento 6? E de comprimento 7?
d) Existem ao todo 377 sequências de comprimento 15, sendo 233 pares e 144 ímpares. Quantas são as sequências de comprimento 16? Dessas, quantas são pares? Não se esqueça de justificar sua resposta.
Resposta:
a) A sequência é 37→38→19→20→10→5→6→3→4→2→1.
b) A única sequência de comprimento 3 é 4→2→1. As sequências de comprimento 4 são 3→4→2→1e 8→4→2→1; elas são obtidas a partir de 4→2→1, a primeira acrescentando 4 - 1= 3 no início da sequência e a segunda acrescentando 2 x 4 = 8 no início da sequência. Do mesmo modo, a sequência ímpar 3→ 4→2→1 dá origem à sequência par 6→3→4→2→1 e a sequência par 8→4→2→1dá origem à sequência ímpar7→8→4→2→1e à sequência par 16→8→4→2→1. Temos assim as três únicas sequências de comprimento 5, sendo duas delas pares e uma ímpar. O raciocínio pode ser representado pelo esquema abaixo.
 |
c) 1a solução: Repetindo o esquema do item anterior, temos:
 |
e assim temos 3 sequências pares e 2 ímpares de comprimento 6 e 5 sequências pares e 3 ímpares de comprimento 7.
2a solução: Observamos que a sequência ímpar de comprimento cinco vai gerar 1 sequência par de comprimento seis; já as 2 sequências pares de comprimento cinco vão gerar 2 sequências pares de comprimento seis e 2 sequências ímpares de comprimento seis. Assim, temos 2 sequências ímpares de comprimento seis e 1 + 2 = 3 sequências pares de comprimento seis, num total de 2 + 3 = 5 sequências de comprimento 6. O mesmo argumento mostra que há 8 sequências de comprimento sete, sendo três ímpares e cinco pares.
Observação: A repetição desse argumento para valores sucessivos do comprimento mostra que, a partir do comprimento 3, o número de sequências ímpares é 0, 1, 1, 2, 3, 5, 8,..., o número de sequências pares é 2, 3, 5, 8, 13,... e o número total de sequências é 3, 5, 8, 13, 21, ..... Cada termo dessas sequências de valores, a partir do terceiro, é a soma dos dois anteriores; vemos assim que essas sequências, com a eventual omissão de termos iniciais, são a sequência 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,..., conhecida como sequência de Fibonacci.
 |
d) 1a solução: As 144 sequências ímpares de comprimento quinze vão gerar 144 sequências pares de comprimento dezesseis; já as 233 sequências pares de comprimento quinze vão gerar 233 sequências pares de comprimento dezesseis e 233 sequências ímpares de comprimento dezesseis. Assim, temos 233 sequências ímpares de comprimento dezesseis e 377 = 233 +144 sequências pares de comprimento dezesseis, num total de 233 + 377 = 610 sequências.
2a solução: A parte da sequência de Fibonacci que nos interessa é 1, 2, 3, 5, 8,....., 144, 233, 377, 610,... . O número de sequências ímpares de comprimento 15 (resp. 16) é o 15o (resp. 16o) termo dessa sequência, que é 144 (resp. 233); o número de sequências pares de comprimento 15 (resp.16) é o 16o (resp. 17o) termo, que é 233 (resp. 377) e o número total é o 17o (resp. 18o) termo, que é 377 (resp. 610).
