Considere a seguinte brincadaeira: escolhe-se um valor inteiro
, se ele for ímpar subtraimos 1 , se for par dividimos por 2 ; repetimos o mesmo processo com o resultado obtido nessa primeira etapa e assim por diante até que o resultado seja 1. Por exemplo, se iniciarmos com o número 13 , devemos subtrair 1 , obtendo 12 , depois dividir por 2 e assim por diante de modo que obtemos a seguinte sequência:
, sendo necessárias 5 estapas até chegarmos no resultado 1. Quantas etapas seriam necessárias para reduzir o número
até 1 segundo o processo descrito acima?
- “Memento, homo, quia pulvis es, et in pulverem reverteris”
- “Memento, homo, quia pulvis es, et in pulverem reverteris”
Passo 1
O enunciado pede para calcular quantas etapas são necessárias para reduzir o número
até
seguindo esta regra iterativa: se o número atual é ímpar, subtrai-se
; se é par, divide-se por
. Informações dadas e objetivo:
- Número inicial:
. - Operações permitidas por etapa: "subtrair
" (se o número for ímpar) ou "dividir por " (se o número for par). - Para cada operação conta-se uma etapa; repetir até obter
. - Precisamos encontrar o total de etapas necessárias.
Passo 2
Observação inicial e padrão a investigar: números da forma
são ímpares para todo inteiro
. Então, ao aplicar a regra a
primeiro fazemos a operação "subtrair
". Vou analisar o que acontece algebraicamente quando começamos com
.
Subtrair
de
:
Fatorando:
Isto mostra que depois de subtrair
obtemos um número par que é exatamente
vezes
.
Passo 3
Como o resultado após a subtração é par, a próxima etapa será dividir por
. Dividindo
por
obtemos:
Portanto, começando de
, duas etapas consecutivas (primeiro subtrair
, depois dividir por
) transformam
em
.
Passo 4
Conseqüência do passo anterior (padrão iterativo): sempre que o número atual tem a forma
com
, aplicando uma etapa de "subtrair
" seguida de uma etapa de "dividir por
" obtemos
. Ou seja, cada par de etapas reduz o expoente
em
.
Passo 5
Quando o expoente chega a
temos
, que é o estado final; o processo então termina. Logo, para ir de
até
precisamos reduzir
até
. O número de reduções do expoente necessárias é
. Cada redução do expoente consome exatamente
etapas (uma subtração e uma divisão), conforme mostrado.
Passo 6
Conclusão geral: o total de etapas necessárias para reduzir
até
é
Aplicando ao caso pedido, com
: