Sociólogos podem obter três respostas possíveis para uma típica pergunta de levantamento como “Você acredita em Papai Noel?” - ou seja: sim, não, nenhuma opinião. Tendo isso em mente, a Sociomagnetic Computer Company decidiu construir um computador para processar os dados do levantamento.
Esse computador tem uma memória ternária, isto é, cada byte (tryte?) consiste em 8 trits, sendo que um trit contém um 0 , um 1 ou um 2 . Quantos trits são necessários para conter um número de 6 bits? Escreva uma expressão para o número de trits necessário para conter n bits.

Passo 1

O enunciado dá estas informações e pede duas coisas:
  • Informação dada: um trit pode tomar três valores: 0,1,2. Um conjunto de t trits tem 3^{t} combinações possíveis. Um número de n bits tem 2^{n} combinações possíveis.
  • Perguntas: (a) quantos trits são necessários para conter um número de 6 bits? (b) escrever uma expressão geral para o número de trits necessário para conter n bits.

Passo 2

Entendendo o que significa “conter” um número de n bits.
  • Um número de n bits pode representar 2^{n} diferentes valores (de 0 a 2^{n}-1).
  • Um conjunto de t trits pode representar 3^{t} diferentes valores (de 0 a 3^{t}-1).
    Para que t trits sejam suficientes para representar qualquer número de n bits devemos ter, necessariamente,
3^{t}\ge 2^{n}.
Isto é a condição básica: o número de estados possíveis com trits tem que ser pelo menos o número de estados que os bits pedem.

Passo 3

Resolver a desigualdade para t. Aplicamos logaritmo (qualquer base serve; aqui uso logaritmo natural \ln) para “trazer o expoente para baixo”:
\ln(3^{t}) \ge \ln(2^{n}).
Usando a propriedade \ln(a^{b})=b\ln a obtemos
t\ln 3 \ge n\ln 2.
Agora isolamos t:
t \ge n\frac{\ln 2}{\ln 3}.
Como t deve ser um número inteiro (número de trits inteiro), precisamos do menor inteiro t que satisfaça essa desigualdade. Isso é exatamente a função teto (ceiling). Assim a expressão exata para o menor t inteiro é
t=\left\lceil n\frac{\ln 2}{\ln 3}\right\rceil.
Também podemos escrever usando logaritmo na base 3, usando \log_{3} (troca de base):
t=\left\lceil n\log_{3}2\right\rceil.
Ambas as formas são equivalentes.

Passo 4

Aplicar ao caso n=6. Primeiro verificação direta com potências inteiras (sem log):
2^{6}=64.
Comparando com potências de 3:
3^{3}=27<64,\qquad 3^{4}=81\ge64.
Portanto t=4 trits já produzem 81 estados, suficientes para os 64 estados dos 6 bits, enquanto 3 trits dão só 27 estados — insuficiente. Logo t=4.

Passo 5

Fazer a conta com logaritmo para confirmar numericamente (opcional, mostra como usar a fórmula):
n\frac{\ln 2}{\ln 3}=6\cdot\frac{\ln 2}{\ln 3}\approx 6\cdot 0{,}63093\approx 3{,}7856,
e então
t=\left\lceil 3{,}7856\right\rceil=4,
compatível com a verificação por potências.

Resposta

4
t=\left\lceil n\frac{\ln 2}{\ln 3}\right\rceil=\left\lceil n\log_{3}2\right\rceil

Exercícios relacionados