Questão 20 (Nível 1) da OBMEP 2016

Question

Josefa brinca de escrever sequências de números. A partir de um número natural maior do que 1, ela procede da seguinte forma para obter o próximo número:

Se o número for par, ela o divide por 2.
Se o número for ímpar e tiver apenas um algarismo, ela soma 1 a esse número e divide o resultado por 2.
Se o número for ímpar e tiver mais de um algarismo, ela apaga o algarismo das unidades.

Josefa repete o procedimento com o número obtido até aparecer o número 1, quando termina a sequência.

Por exemplo, a sequência que começa com 1101 é formada por sete números: 1101 \rightarrow 110 \rightarrow 55 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 1.

Quantas são as sequências formadas por três números?

Ilustração de uma menina ruiva (Josefa) sentada a uma mesa escrevendo em um caderno a sequência: "1101 -> 110 -> 55 -> 5 -> 3 -> 2 -> 1".

A
7
B
12
C
14
D
25
E
37

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 20 (Nível 1) da OBMEP 2016

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

Josefa brinca de escrever sequências de números. A partir de um número natural maior do que 1, ela procede da seguinte forma para obter o próximo número:

Se o número for par, ela o divide por 2.
Se o número for ímpar e tiver apenas um algarismo, ela soma 1 a esse número e divide o resultado por 2.
Se o número for ímpar e tiver mais de um algarismo, ela apaga o algarismo das unidades.

Josefa repete o procedimento com o número obtido até aparecer o número 1, quando termina a sequência.

Por exemplo, a sequência que começa com 1101 é formada por sete números: 1101 \rightarrow 110 \rightarrow 55 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 1.

Quantas são as sequências formadas por três números?

Ilustração de uma menina ruiva (Josefa) sentada a uma mesa escrevendo em um caderno a sequência: "1101 -> 110 -> 55 -> 5 -> 3 -> 2 -> 1".

A
7
B
12
C
14
D
25
E
37

Escolha uma alternativa para conferir o gabarito.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

Solução 1: Uma sequência com três números é obtida após a aplicação de dois procedimentos a partir do primeiro número, finalizando no terceiro número igual a 1. Vamos fazer a contagem das sequências a partir da quantidade de algarismos do número inicial.

número inicial com 3 algarismos: nesse caso o único procedimento usado foi o de apagar o algarismo das unidades (duas vezes, consecutivamente). Nesta situação, o número inicial é ímpar (5 possibilidades para o algarismo das unidades), com o algarismos das dezenas também ímpar (também 5 possibilidades para o algarismo das dezenas), e com o algarismo das centenas igual a 1 (acima de 199, não obtemos o 1 como terceiro número aplicando apenas 2 procedimentos). Assim, existem 5 \times 5 \times 1 = 25 números de três algarismos que geram uma sequência formada por três números.
número inicial com 2 algarismos: necessariamente usamos dois procedimentos diferentes para formá-la: apagamos os algarismos das unidades (se iniciar por um ímpar) ou dividimos por 2 (se iniciar por um par), nessa ordem ou vice-versa.
- Se o primeiro número for ímpar, o algarismo das dezenas é 2 (pois deve ser o resultado obtido após apagar o seu algarismo das unidades). Nesse caso, temos 5 possibilidades.
- Se o primeiro número for par, o segundo é a sua metade. Nesse caso, o segundo termo deve ser ímpar (para usarmos, em continuação, o procedimento de apagar o algarismo das unidades). Como, após apagar as unidades, devemos obter 1, o número obtido no estágio intermediário é ímpar entre 10 e 20. Nesse caso, também temos 5 possibilidades.

Assim, existem 5 + 5 = 10 números de dois algarismos que geram uma sequência formada por três números.

número inicial com 1 algarismo: temos duas sequências, uma com o número inicial igual a 4 e outra iniciando por 3.

Logo, o número de sequências formadas por três números é 25 + 10 + 2 = 37.

A tabela abaixo mostra as possíveis sequências formadas por três números. Para isso, usamos as letras u e d, para representar, respectivamente, o algarismo das unidades e das dezenas do número inicial.

Número inicial	Observação	1º procedimento	Número intermediário	2º procedimento	Quantidade de sequências
1du	d e u ímpares	apaga unidade	1d	apaga unidade	5 \times 5 = 25
2u	u ímpar	apaga unidade	2	divide por 2	5
du	u par	divide por 2	ímpar entre 10 e 20	apaga unidade	5
u=4		divide por 2	2	divide por 2	1
u=3		soma 1 e divide por 2	2	divide por 2	1
total de sequências					37

Solução 2: As sequências descritas no enunciado que começam com números de apenas um algarismo são:

2 \to 1, 3 \to 2 \to 1, 4 \to 2 \to 1, 5 \to 3 \to 2 \to 1, 6 \to 3 \to 2 \to 1, 7 \to 4 \to 2 \to 1 e 8 \to 4 \to 2 \to 1 e 9 \to 5 \to 3 \to 2 \to 1.

Destas, somente duas têm três termos: a que começa com 3 e a que começa com 4.

Há apenas as seguintes sequências com dois termos: 2 \to 1, 11 \to 1, 13 \to 1, 15 \to 1, 17 \to 1 e 19 \to 1. Utilizando-as, há dois procedimentos para se obter sequências com três termos:

Colocando-se como primeiro termo da sequência o dobro dos números iniciais das sequências com dois termos exibidas acima:

4 \to 2 \to 1, 22 \to 11 \to 1, 26 \to 13 \to 1, 30 \to 15 \to 1, 34 \to 17 \to 1 e 38 \to 19 \to 1.

Observe que 4 \to 2 \to 1 já havia sido contada antes e, portanto, no total, até agora, temos sete sequências de três termos.

Colocando-se como primeiro termo da sequência números iniciados com 2 (ou seja, com 2 na casa das dezenas) ou 11, 13, 15, 17 ou 19 (ou seja, com 1 na casa das centenas e um algarismo ímpar na casa das dezenas) e terminados com um número ímpar na casa das unidades:

21 \to 2 \to 1, 23 \to 2 \to 1, 25 \to 2 \to 1, 27 \to 2 \to 1, 29 \to 2 \to 1
111 \to 11 \to 1, 113 \to 11 \to 1, 115 \to 11 \to 1, 117 \to 11 \to 1, 119 \to 11 \to 1
131 \to 13 \to 1, 133 \to 13 \to 1, 135 \to 13 \to 1, 137 \to 13 \to 1, 139 \to 13 \to 1
151 \to 15 \to 1, 153 \to 15 \to 1, 155 \to 15 \to 1, 157 \to 15 \to 1, 159 \to 15 \to 1
171 \to 17 \to 1, 173 \to 17 \to 1, 175 \to 17 \to 1, 177 \to 17 \to 1, 179 \to 17 \to 1
191 \to 19 \to 1, 193 \to 19 \to 1, 195 \to 19 \to 1, 197 \to 19 \to 1, 199 \to 19 \to 1

Assim, ao todo temos 7 + 30 = 37 sequências de três termos.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Vamos trabalhar de trás para frente. Uma sequência de três números tem a forma a \rightarrow b \rightarrow 1, com a e b maiores que 1 (a sequência começa em número maior que 1 e termina quando aparece o 1).

Quem chega ao 1 em um passo? Pelas regras:

Par: n/2=1 dá n=2.
Ímpar de um algarismo: (n+1)/2=1 dá n=1, que não serve (o 1 encerra a sequência).
Ímpar com mais de um algarismo: apagar a unidade dá 1 se n=1x com x ímpar, ou seja, 11, 13, 15, 17, 19.

Logo b \in \{2, 11, 13, 15, 17, 19\}.

Quem chega a cada b em um passo? Contamos os a>1 cujo próximo número é b:

Para b=2: o dobro, 4; o ímpar de um algarismo com (a+1)/2=2, ou seja, 3; ímpar com mais de um algarismo que, sem a unidade, vira 2: impossível, pois seria 21, 23, 25, 27, 29 (todos ímpares, ok, valem). Então a\in\{4,3,21,23,25,27,29\}: 7 sequências.
Para b=11: o dobro, 22; ímpar com dois algarismos termina em 11 só com 111, 113, 115, 117, 119 (apagando a unidade). Então 22 e esses cinco: 6 sequências. Ímpar de um algarismo não dá 11.
Para b=13,15,17,19: cada um tem 6 sequências (o dobro e cinco ímpares de três algarismos b\,x com x ímpar), ou seja, 4\cdot 6=24.

Os números b de 11 a 19 são ímpares, então só entram pelo dobro e pela remoção do algarismo.

Total: 7+6+24. Revendo: para b=2 há 7; para cada um dos cinco valores 11, 13, 15, 17, 19 há 6, o que dá 30. Total =7+30=37.

Alternativa E.

Por que as outras alternativas estão erradas

AConta apenas as sequências que passam pelo 2 como segundo número.
BIgnora os ímpares de três algarismos que perdem a unidade.
CNúmero muito baixo, desconsidera vários predecessores de 11 a 19.
DEsquece parte dos predecessores, como os ímpares 21 a 29 do número 2.

Assunto: Sequências e padrões.

Reportar erro na resolução

Esta questão também caiu em

OBMEP 2016 · Questão 18 (Nível 2)Quantas são as sequências formadas por três números?

Ver como caiu na prova

Questão 20 no caderno Nível 1 da OBMEP 2016

Fonte: OBMEP 2016 · Nível 1. Prova oficial ↗