Questão 4 (Nível 2) 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 \rightarrow 22 \rightarrow 11 \rightarrow 12 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 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 4 (Nível 2) da 2ª fase da OBMEP 2011

Nível 2 · 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 \rightarrow 22 \rightarrow 11 \rightarrow 12 \rightarrow 6 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 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 \to 38 \to 19 \to 20 \to 10 \to 5 \to 6 \to 3 \to 4 \to 2 \to 1 .

b) A única sequência de comprimento 3 é 4 \to 2 \to 1. As sequências de comprimento 4 são 3 \to 4 \to 2 \to 1 e 8 \to 4 \to 2 \to 1; elas são obtidas a partir de 4 \to 2 \to 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 \to 4 \to 2 \to 1 dá origem à sequência par 6 \to 3 \to 4 \to 2 \to 1; a sequência par 8 \to 4 \to 2 \to 1 dá origem à sequência ímpar 7 \to 8 \to 4 \to 2 \to 1 e à sequência par 16 \to 8 \to 4 \to 2 \to 1. Temos assim as três únicas sequências de comprimento 5, sendo 2 pares e 1 ímpar. O raciocínio pode ser representado pelo esquema abaixo.

[Figura: Esquema em árvore ilustrando a formação das sequências a partir do 1 à direita: 1 se conecta a 2, que se conecta a 4; 4 bifurca em 3 (que liga a 6) e 8 (que bifurca em 7 e 16).]

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

[Figura: Esquema em árvore estendendo as sequências até os comprimentos 6 e 7: a partir do 6 ramificam-se 5 (que vai a 10) e 12 (que bifurca em 11 e 24); a partir do 7 ramifica-se 14 (que bifurca em 13 e 28); a partir do 16 ramificam-se 15 (que vai a 30) e 32 (que bifurca 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^a 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 cinco dã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^a 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^a 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^o (resp. 16^o) termo dessa sequência, que é 144 (resp. 233); o número de sequências pares de comprimento 15 (resp.16) é o 16^o (resp. 17^o) termo, que é 233 (resp. 377) e o número total é o 17^o (resp. 18^o) termo, que é 377 (resp. 610).

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Se o número é ímpar, soma-se 1; se é par, divide-se por 2:

37 \to 38 \to 19 \to 20 \to 10 \to 5 \to 6 \to 3 \to 4 \to 2 \to 1

A sequência tem comprimento 11.

37, 38, 19, 20, 10, 5, 6, 3, 4, 2, 1.

b) Vamos construir as sequências de trás para frente, a partir do 1, que é o último termo. Para achar quem pode vir antes de um número n:

2n sempre serve, pois é par e 2n \div 2 = n;
n-1 serve só se for ímpar (ou seja, n par), pois (n-1)+1 = n.

O 1 não tem antecessor, porque a sequência para nele.

Comprimento 2: apenas o 2 (par).
Comprimento 3: antecessores do 2 são o 4 (o 1 não conta). Fica só o 4.
Comprimento 4: antecessores do 4 são 8 (par) e 3 (ímpar).
Comprimento 5: antecessores do 8 são 16 (par) e 7 (ímpar). O antecessor do 3 é o 6 (par), pois 3 é ímpar e 2 é par, então não serve.

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.

Pares: 16, 8, 4, 2, 1 e 6, 3, 4, 2, 1. Ímpar: 7, 8, 4, 2, 1.

c) Seguimos a mesma regra, com os números iniciais do comprimento 5: 16, 6 (pares) e 7 (ímpar).

Comprimento 6:

16 gera 32 (par) e 15 (ímpar);
6 gera 12 (par) e 5 (ímpar);
7 gera só 14 (par).

São 3 pares (32, 12, 14) e 2 ímpares (15, 5), 5 no total.

Comprimento 7: partimos de 32, 12, 14 (pares) e 15, 5 (ímpares).

32 gera 64 e 31;
12 gera 24 e 11;
14 gera 28 e 13;
15 gera 30;
5 gera 10.

São 5 pares (64, 24, 28, 30, 10) e 3 ímpares (31, 11, 13), 8 no total.

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

d) Observe o que acontece de um comprimento para o seguinte (a partir do comprimento 3):

Todo número inicial de uma sequência gera um antecessor par (o dobro). Logo, o número de sequências pares de comprimento k+1 é igual ao total de sequências de comprimento k.
Só os números pares geram também um antecessor ímpar (n-1). Logo, o número de sequências ímpares de comprimento k+1 é igual ao número de pares de comprimento k.

Confere com os resultados anteriores: do comprimento 5 (2 pares, 1 ímpar, total 3) saem 3 pares e 2 ímpares no comprimento 6.

Para o comprimento 16, com 233 pares e 144 ímpares no comprimento 15:

pares: 233+144 = 377;
ímpares: 233;
total: 377+233 = 610.

Existem 610 sequências de comprimento 16, sendo 377 pares.

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 4 no caderno Nível 2 da 2ª fase da OBMEP 2011

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