Questão 18 (Nível 2) 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.

Ilustração de uma menina sentada à mesa escrevendo em um caderno a sequência 1101 -> 110 -> 55 -> 5 -> 3 -> 2 -> 1.

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

A
7
B
12
C
14
D
25
E
37

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 18 (Nível 2) da OBMEP 2016

Nível 2 · 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.

Ilustração de uma menina sentada à mesa escrevendo em um caderno a sequência 1101 -> 110 -> 55 -> 5 -> 3 -> 2 -> 1.

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

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

Uma sequência com três números tem a forma n \rightarrow a \rightarrow 1, com n>1 e a>1. Vamos contar de trás para frente.

Quem vai direto para 1? Um número par só dá 1 se for 2. Um ímpar de um algarismo dá 1 só se for 1, que não serve, pois a sequência já terminaria. Um ímpar com mais de um algarismo dá 1 se, ao apagar a unidade, sobrar 1: são 11, 13, 15, 17 e 19. Então a \in \{2, 11, 13, 15, 17, 19\}, ou seja, 6 valores.
Quem vai para cada a? Há três tipos de antecessor:

o par 2a (sempre existe);
o ímpar de um algarismo 2a-1 (só se for ímpar de um algarismo, ou seja, a \le 5);
os ímpares 10a+d, com d \in \{1,3,5,7,9\} (5 números).

Contagem:

a=2: 4; 3; 21, 23, 25, 27, 29. Total 7.
a=11, 13, 15, 17, 19: o par 2a e os 5 números 10a+d (aqui 2a-1 \geq 21 tem dois algarismos e não vale). Total 6 para cada.

Como cada número n tem um único próximo número, os antecessores de a diferentes nunca se repetem.

Total: 7 + 5\cdot 6 = 37.

Alternativa E.

Pegadinha: Quem inclui o 1 como antecessor de 1 (pois (1+1)/2=1) ou esquece o ímpar de um algarismo (o 3 que leva a 2) erra a contagem.

Por que as outras alternativas estão erradas

AConta apenas os 6 números que levam a 1 (mais um), sem contar os antecessores deles.
BConsidera só os pares e alguns ímpares, deixando de fora os ímpares do tipo 10a+d.
CSubconta os antecessores dos números 11 a 19, esquecendo vários ímpares do tipo 10a+d.
DErra ao incluir ou excluir casos, por exemplo contando 3 antecessores a menos nos casos de a de dois algarismos.

Assuntos: Sequências e padrões, Princípio fundamental da contagem.

Reportar erro na resolução

Esta questão também caiu em

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

Ver como caiu na prova

Questão 18 no caderno Nível 2 da OBMEP 2016

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