Questão 6 (Nível 1) da 2ª fase da OBMEP 2011

Question

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 \to 22 \to 11 \to 12 \to 6 \to 3 \to 4 \to 2 \to 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.

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 6 (Nível 1) da 2ª fase da OBMEP 2011

Nível 1 · Matemática: Sequências e padrões

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 \to 22 \to 11 \to 12 \to 6 \to 3 \to 4 \to 2 \to 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.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a) A sequência é 37 \rightarrow 38 \rightarrow 19 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1.

b) A única sequência de comprimento 3 é 4 \rightarrow 2 \rightarrow 1. As sequências de comprimento 4 são 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 e 8 \rightarrow 4 \rightarrow 2 \rightarrow 1; elas são obtidas a partir de 4 \rightarrow 2 \rightarrow 1, a primeira acrescentando 4 - 1 = 3 à esquerda e a segunda acrescentando 2 \times 4 = 8 à esquerda. Do mesmo modo, a sequência ímpar 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 dá origem à sequência par 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1; a sequência par 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 dá origem à sequência ímpar 7 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 e à sequência par 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1. Temos assim as três únicas sequências de comprimento 5, sendo 2pares e 1 ímpar. O raciocínio pode ser representado pelo esquema abaixo.

[Figura: Diagrama em árvore orientado da direita para a esquerda, iniciando em 1 e passando sucessivamente por 2 e 4. A partir de 4, ramifica-se para 3 (que leva a 6) e para 8 (que se divide em 7 e 16).]

c) 1ª solução: Repetindo o esquema do item anterior, temos:

[Figura: Diagrama em árvore ramificando da direita para a esquerda a partir do número 1, passando por 2 e 4. De 4, bifurca para 3 e 8. De 3 vai para 6, que se divide em 5 (levando a 10) e 12 (que se divide em 11 e 24). De 8 bifurca para 7 (levando a 14, que se divide em 13 e 28) e 16 (que se divide em 15, levando a 30, e 32, que se divide em 31 e 64).]

e assim temos 3 sequências pares e 2 ímpares de comprimento 6 e 5 sequências pares e 3 ímpares de comprimento 7.

2ª solução: Observamos que a sequência ímpar de comprimento cinco dá origem a 1 sequência par de comprimento seis; já as 2 sequências pares de comprimento cincodão origem a 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. Apresentamos esse resultado na tabela a seguir.

comprimento	5	6	7	...	15	16
Ímpares	1	2	3	...	144	233
pares	2	2 + 1 = 3	3 + 2 = 5	...	233	233 + 144 = 377
total	1 + 2 = 3	2 + 3 = 5	3 + 5 = 8	...	144 + 233 = 377	233 + 377 = 610

d) 1ª solução: As 144 sequências ímpares de comprimento quinze dão origem a 144 sequências pares de comprimento dezesseis; já as 233 sequências pares de comprimento quinze dão origem a 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.

2ª 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 15º (resp. 16º) termo dessa sequência, que é 144 (resp. 233); o número de sequências pares de comprimento 15 (resp.16) é o 16º (resp. 17º) termo, que é 233 (resp. 377) e o número total é o 17º (resp. 18º) termo, que é 377 (resp. 610).

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Aplicando as regras: se é ímpar, soma 1; se é par, divide por 2.

37\to38\to19\to20\to10\to5\to6\to3\to4\to2\to1

Sequência: 37, 38, 19, 20, 10, 5, 6, 3, 4, 2, 1.

b) Vamos de trás para a frente, a partir do 1. Um número n pode ser precedido por:

2n, que é par e, dividido por 2, dá n;
n-1, se n-1 for ímpar (isso exige n par), pois n-1 somado a 1 dá n. O número 1 não serve, porque a sequência termina nele.

Assim:

Comprimento 2: 2\to1.
Comprimento 3: antes do 2 só vem o 4, então 4\to2\to1.
Comprimento 4: antes do 4 vêm o 8 e o 3. Ficam 8\to4\to2\to1 e 3\to4\to2\to1.
Comprimento 5: antes do 8 vêm o 16 e o 7; antes do 3 vem só o 6, pois o 3 é ímpar.

As sequências de comprimento 5 são:

pares: 16\to8\to4\to2\to1 e 6\to3\to4\to2\to1;
ímpar: 7\to8\to4\to2\to1.

c) Usamos o raciocínio do item d, com a lista completa por trás dele.

Comprimento 6: antes de 16, 7 e 6 vêm

32 e 15 (antes do 16);
14 (antes do 7);
12 e 5 (antes do 6).

São três sequências começando em número par (32, 14, 12) e duas em número ímpar (15, 5). Total: 5.

Comprimento 7: usando a regra do item d, o número de pares é 3+2=5 e o de ímpares é 3. Total: 8.

Comprimento 6: 3 pares e 2 ímpares. Comprimento 7: 5 pares e 3 ímpares.

d) Seja uma sequência de comprimento 16.

Se ela começa com um número par 2m, o segundo termo é m, e a partir dele temos uma sequência de comprimento 15. Cada sequência de comprimento 15 (par ou ímpar) gera exatamente uma sequência par de comprimento 16, multiplicando seu primeiro termo por 2. Logo, o número de pares de comprimento 16 é 233+144=377.
Se ela começa com um número ímpar x, o segundo termo é x+1, que é par. Então x+1 começa uma sequência par de comprimento 15. Cada par de comprimento 15 gera exatamente uma ímpar de comprimento 16, subtraindo 1 do primeiro termo. Logo, o número de ímpares de comprimento 16 é 233.

Total: 377+233=610.

Existem 610 sequências de comprimento 16, sendo 377 pares (e 233 ímpares).

Assunto: Sequências e padrões.

Reportar erro na resolução

Esta questão também caiu em

Ver como caiu na prova

Questão 6 no caderno Nível 1 da 2ª fase da OBMEP 2011

Fonte: OBMEP 2ª fase 2011 · Nível 1. Prova oficial ↗