Considere a função definida por
T(n)=ll 3 n+12 & para n ímpar n2 & para n par í
A conjectura 3 n+1 é a afirmação de que a partir de qualquer inteiro n>1, a sequência de iterações T(n), T(T(n)), T(T(T(n))), …, finalmente atinge o inteiro 1 e, posteriormente, passa pelos valores 1 e 2. Isto foi verificado para todo n<10^6. Confirme esta conjectura nos casos em que n=21 e n=23.

Passo 1

Beleza, a questão é sobre a famosa conjectura “3n+1” (ou problema de Collatz). Recebemos a função
T(n)= 3n+12,&se $n$ é ímpar, n2,&se $n$ é par, éíé
e precisamos mostrar que, partindo de e de , as iterações de chegam em 1 (e depois passam por 2). Para resolver isso, vamos aplicar passo a passo a definição de até aparecer o 1.

Passo 2

Vamos começar com T(21)=3cdot21+12=63+12=642=32 .
  1. T(32)=322=16 é ímpar, então T(16)=162=8
  2. T(8)=82=4 é par, logo T(4)=42=2
  3. T(2)=22=1 é par,
  4. é par,
  5. é par,
  6. é par,
Pronto, a partir de 21 chegamos em 1 depois de algumas aplicações de .

Passo 3

Agora T(23)=3cdot23+12=69+12=702=35 :
  1. T(35)=3cdot35+12=105+12=1062=53 é ímpar, T(53)=3cdot53+12=159+12=1602=80
  2. T(80)=802=40 é ímpar, T(40)=20, T(20)=10, T(10)=5
  3. T(5)=3cdot5+12=15+12=8 é ímpar, 8to4to2to1
  4. é par,
  5. (tudo par até chegar em 5):
  6. é ímpar,
  7. A partir de voltamos ao mesmo ciclo de pares:
Logo, começando em 23 também chegamos em 1.

Passo 4

A gente aplicou direitinho a regra de Collatz ( par vs ímpar) e viu que, tanto para quanto para , a sequência atinge o valor 1, depois 2, e assim por diante. Isso confirma a conjectura para esses casos específicos.

Resposta

Para e para , as iterações de chegam em 1 (e depois passam por 2), confirmando a conjectura nesses casos.

Exercícios relacionados