Questão 2 (Nível 3) 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 2 (Nível 3) da 2ª fase da OBMEP 2011

Nível 3 · 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 \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 no início da sequência e a segunda acrescentando 2 \times 4 = 8 no início da sequência. 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 e 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 duas delas pares e uma ímpar. O raciocínio pode ser representado pelo esquema abaixo.

[Figura: Esquema em árvore gerando sequências da direita para a esquerda: o número 1 liga-se ao 2, que liga-se ao 4; o 4 ramifica-se para 3 e 8; o 3 liga-se ao 6; o 8 ramifica-se para 7 e 16.]

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

[Figura: Esquema em árvore estendendo as ramificações até o comprimento 7. A partir de 1 - 2 - 4: 4 ramifica em 3 e 8; 3 liga a 6, que ramifica em 5 (ligando a 10) e 12 (ramificando em 11 e 24); 8 ramifica em 7 (ligando a 14, que ramifica em 13 e 28) e 16 (ramificando em 15, que liga a 30, e 32, que ramifica 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 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.

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 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.

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) Seguimos a regra: ímpar soma 1, par divide por 2.

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

Sequência de comprimento 11, como acima.

b) Vamos de trás para frente. Os predecessores de um número n numa sequência são:

2n, que é par e dividido por 2 dá n;
n-1, se n for par, pois n-1 é ímpar e somando 1 dá n.

O número 1 só pode ser o fim da sequência, então 1\to2\to1 não vale.

Comprimento 2: 2\to1.
Comprimento 3: 4\to2\to1.
Comprimento 4: os predecessores de 4 são 8 e 3.
Comprimento 5: os predecessores de 8 são 16 e 7, e o de 3 é só 6.

As sequências de comprimento 5 são:

16\to8\to4\to2\to1 (par);
6\to3\to4\to2\to1 (par);
7\to8\to4\to2\to1 (ímpar).

Resposta: as três sequências acima.

c) Continuamos o processo anterior.

Comprimento 6: os predecessores de 16 são 32 e 15; o de 7 é 14; os de 6 são 12 e 5. Os inícios possíveis são 32, 15, 14, 12 e 5. Pares: 32, 14 e 12, ou seja, 3. Ímpares: 15 e 5, ou seja, 2.

Comprimento 7: os predecessores de 32 são 64 e 31; o de 15 é 30; os de 14 são 28 e 13; os de 12 são 24 e 11; o de 5 é 10. Os inícios possíveis são 64, 31, 30, 28, 13, 24, 11 e 10. Pares: 64, 30, 28, 24 e 10, ou seja, 5. Ímpares: 31, 13 e 11, ou seja, 3.

Resposta: comprimento 6: 3 pares e 2 ímpares; comprimento 7: 5 pares e 3 ímpares.

d) Toda sequência de comprimento n+1 nasce de uma de comprimento n acrescentando um número na frente.

Se a de comprimento n começa com m, podemos acrescentar 2m. Isso vale sempre e dá uma sequência par. Logo, os pares de comprimento n+1 são tantos quanto todas as de comprimento n.
Se m é par, podemos acrescentar m-1 (ímpar). Isso dá uma sequência ímpar. Logo, os ímpares de comprimento n+1 são tantos quanto os pares de comprimento n. (Aqui m=2 não conta, pois só aparece em comprimento 2.)

Com 233 pares, 144 ímpares e 377 no total no comprimento 15:

pares de comprimento 16: 377;
ímpares de comprimento 16: 233;
total: 377+233=610.

Confira com os dados anteriores: do comprimento 6 para o 7, os pares passaram de 3 para 5=3+2 e os ímpares de 2 para 3 (os pares do comprimento 6). A regra funciona.

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

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