Sejam m=\left(r_{n} r_{n-1} \ldots r_{0}\right)_{b}, m^{\prime}=\left(s_{n^{\prime}}, s_{n^{\prime}-1} \ldots s_{0}\right)_{b}. Provar que, se n<n^{\prime}, então m<m^{\prime}. Dar um critério para comparar m e m^{\prime} em geral.

Passo 1

Enunciado reescrito e dados fornecidos: temos dois números escritos na base b,
m=\left(r_{n} r_{n-1} \ldots r_{0}\right)_{b} \qquad\text{e}\qquad m'=\left(s_{n'} s_{n'-1} \ldots s_{0}\right)_{b}.
As informações relevantes são:
  • Cada dígito satisfaz 0 \le r_i \le b-1 e 0 \le s_i \le b-1.
  • As representações estão normalizadas, isto é, r_n \neq 0 e s_{n'} \neq 0 (os dígitos mais significativos não são zero).
  • A primeira pergunta a provar: se n < n' então m < m'.
  • A segunda pergunta: dar um critério geral para comparar m e m' (ou seja, como decidir qual é maior em todos os casos).

Passo 2

Entendendo a notação posicional (a “aula rápida”): o número m na base b significa
m = \sum_{i=0}^{n} r_i b^i = r_n b^n + r_{n-1} b^{n-1} + \cdots + r_1 b + r_0,
e análogamente
m' = \sum_{i=0}^{n'} s_i b^i = s_{n'} b^{n'} + s_{n'-1} b^{n'-1} + \cdots + s_1 b + s_0.
Aqui cada termo r_i b^i representa a contribuição do dígito r_i na posição de peso b^i. Como r_n e s_{n'} são não nulos, b^n e b^{n'} são as potências mais altas que aparecem.

Passo 3

Limite superior para m: como cada r_i \le b-1, temos
m \le \sum_{i=0}^{n} (b-1)b^i = (b-1)\sum_{i=0}^{n} b^i.
Recordando a soma da progressão geométrica, para b\neq 1,
\sum_{i=0}^{n} b^i = \frac{b^{n+1}-1}{b-1}.
Substituindo,
m \le (b-1)\cdot\frac{b^{n+1}-1}{b-1} = b^{n+1}-1.
Portanto obtemos o limite útil
m \le b^{n+1}-1.

Passo 4

Limite inferior para m': como s_{n'}\ge 1 (dígito mais significativo não zero), a menor contribuição possível da casa mais significativa é 1\cdot b^{n'}. Assim
m' \ge b^{n'}.

Passo 5

Comparando as potências quando n<n': como n<n' implica n+1 \le n', e para b\ge 2 temos b^{n+1} \le b^{n'}. Daí
b^{n+1}-1 < b^{n'}.
(Explicação rápida: b^{n+1}\le b^{n'} e subtraindo 1 de b^{n+1} fica estritamente menor que b^{n'}.)

Passo 6

Concluindo a primeira parte: juntando os resultados dos passos anteriores temos
m \le b^{n+1}-1 < b^{n'} \le m'.
Logo m < m'. Isso prova a afirmação pedida: se n<n' então m<m'.

Passo 7

Agora o critério geral de comparação (ideia antes da prova formal): comparar primeiro o número de dígitos (isto é, n vs n'). Se forem diferentes, o número com mais dígitos é maior. Se tiverem o mesmo número de dígitos ( n=n'), comparar os dígitos da esquerda (mais significativos) para a direita até achar o primeiro dígito diferente — aí o sinal desse dígito diferente determina qual número é maior. A seguir faço a prova limpa desse critério.

Passo 8

Prova formal do critério quando n=n': suponha n=n'. Se todos os dígitos forem iguais, r_i=s_i para todo i e então m=m'. Caso contrário, existe um índice k tal que r_k\ne s_k; escolha k como o maior índice onde diferem (isto é, o mais significativo diferente). Então para todo i>k temos r_i=s_i, e para i=k temos r_k\ne s_k. Escrevemos a diferença
m-m'=\sum_{i=0}^{n}(r_i-s_i)b^i = (r_k-s_k)b^k + \sum_{i=0}^{k-1}(r_i-s_i)b^i.
A ideia é que o termo principal (r_k-s_k)b^k domina a soma dos termos de ordem inferior. Vamos boundear o termo “resto”:
\left|\sum_{i=0}^{k-1}(r_i-s_i)b^i\right| \le \sum_{i=0}^{k-1}|r_i-s_i|b^i \le \sum_{i=0}^{k-1}(b-1)b^i = b^k-1.
Logo o resto tem magnitude estritamente menor que b^k. Assim se r_k-s_k>0 então
m-m' \ge 1\cdot b^k - (b^k-1) = 1,
portanto m>m'. Se r_k-s_k<0 então
m-m' \le -1\cdot b^k + (b^k-1) = -1,
portanto m<m'. Isso mostra que o sinal de m-m' é o sinal de r_k-s_k: o dígito mais significativo distinto determina qual número é maior.

Passo 9

Resumo do critério prático (o que usar na prova ou em um exercício, passo a passo):
  • Compare n e n' (número de dígitos menos 1). Se n<n' então m<m'. Se n>n' então m>m'.
  • Se n=n', procure o maior índice k tal que r_k\ne s_k. Então:
    • se r_k<s_k temos m<m';
    • se r_k>s_k temos m>m';
    • se não existe tal k (todos os dígitos iguais) então m=m'.
      Exemplos rápidos: na base 10, 99<100 porque 99 tem menos dígitos; e 345<367 porque ambos têm 3 dígitos, o primeiro dígito igual 3, o segundo difere com 4<6.

Resposta

Se n<n' então m<m'.\nCritério geral: se n<n' então m<m'; se n>n' então m>m'. Se n=n' então tome o maior índice k com r_k\ne s_k; o sinal de r_k-s_k determina a comparação: se r_k<s_k então m<m', se r_k>s_k então m>m', e se não existir tal k então m=m'.

Exercícios relacionados