56Potências

Solução de Problema 56.1.

1. Os grãos dobram de casa em casa a partir de $1 = 2^0$: a casa $k$ leva $2^{k-1}$ grãos (Definição 56.1). A casa $64$ leva $2^{63}$.

2. $S_1 = 1$, $S_2 = 1 + 2 = 3$, $S_3 = 3 + 4 = 7$, $S_4 = 7 + 8 = 15$, $S_5 = 15 + 16 = 31$: sempre um a menos que a potência de $2$ seguinte ($2$, $4$, $8$, $16$, $32$). Conjectura: $S_n = 2^n - 1$.

3. Dobrar cada termo de $S_n$ sobe cada potência em um ($2 \times 2^{k} = 2^{k+1}$):

Subtraindo a primeira linha da segunda, cada termo de $2$ a $2^{n-1}$ aparece nas duas e se cancela:

4. O total é $S_{64} = 2^{64} - 1$ grãos. Uma sexagésima quinta casa levaria $2^{64}$ grãos: o tabuleiro inteiro carrega exatamente um grão a menos do que essa única casa carregaria.

5. A primeira metade leva $S_{32} = 2^{32} - 1$ grãos. O tabuleiro inteiro leva $2^{64} - 1$, então a segunda metade leva

(pondo $2^{32}$ em evidência e usando $2^{32} \times 2^{32} = 2^{64}$, Teorema 56.3): exatamente $2^{32}$ vezes a primeira metade.

6. Pelas regras dos expoentes, $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Como $2^{10} = 1024 > 10^3$,

7. Mais de $1.6 \times 10^{19}$ grãos a $5 \times 10^{-2}$ g cada:

Dividindo por $10^6$ g por tonelada: mais de $8 \times 10^{11}$ toneladas — oitocentos bilhões de toneladas.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$: o rei prometeu pelo menos mil anos da colheita mundial inteira de hoje. (A lenda conta que os conselheiros dele lhe disseram isso.)

9. $2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524\,288 < 10^6$, enquanto $2^{20} = \left(2^{10}\right)^2 = 1024^2 = 1\,048\,576 > 10^6$. Então o menor expoente é $n = 20$: vinte duplicações passam do milhão.

10. O pagamento do dia $n$ é $2^{n-1}$ centavos (dia 1: $2^0 = 1$). Ora,

Então o pagamento diário passa pela primeira vez de $10^8$ centavos quando $n - 1 = 27$: no dia $28$.

11. $21 = 16 + 4 + 1$: pesos de $16$, $4$ e $1$ g. $27 = 16 + 8 + 2 + 1$: pesos de $16$, $8$, $2$ e $1$ g.

12. Pela questão 3, os pesos $1, 2, 4, 8$ juntos pesam $S_4 = 2^4 - 1 = 15$ g. Então, sem o peso de $16$ g, a comerciante não consegue passar de $15$ g: qualquer alvo de $16$ g ou mais tem de usá-lo. E um alvo de $15$ g ou menos não pode usá-lo, já que o peso de $16$ g sozinho já ultrapassa o alvo. A escolha do maior peso é, portanto, forçada. O que resta é um alvo de no máximo $15$ g, para ser formado com $1, 2, 4, 8$ — e o mesmo argumento se repete: o $8$ é forçado (usado se o alvo restante for $\geq 8$, não usado caso contrário, porque $1 + 2 + 4 = 7$), depois o $4$ (porque $1 + 2 = 3$), depois o $2$, depois o $1$.

13. Seguindo as escolhas forçadas, o alvo restante depois de cada etapa é no máximo o total dos pesos que sobram, então o processo termina com resto $0$: todo alvo de $1$ a $31$ é alcançado. E, como toda escolha pelo caminho foi forçada, nenhuma outra seleção de pesos alcança o mesmo alvo: a escrita de cada número de $1$ a $31$ como soma de potências de $2$ distintas existe e é única.

14. Os seis pesos totalizam $S_6 = 2^6 - 1 = 63$ g, e o mesmo argumento de escolha forçada cobre todo alvo de $1$ a $63$ g. Para $45$: o alvo é $\geq 32$, então use o $32$; resta $13 < 16$, então pule o $16$; use o $8$ (resta $5$), use o $4$ (resta $1$), pule o $2$, use o $1$:

15. Escolher um $0$ ou um $1$ em cada uma das $64$ casas é escolher que potências $2^0, 2^1, \dots, 2^{63}$ entram numa soma — exatamente a pesagem da comerciante com $64$ pesos. O menor número guardável é $0$ (todas as casas em $0$); o maior é a soma de todas as potências, que é o total do rei: $S_{64} = 2^{64} - 1$ (Parte I). Pelo argumento da escolha forçada, todo número inteiro entre eles é alcançado exatamente uma vez: uma máquina de $64$ bits guarda precisamente os números inteiros de $0$ a $2^{64} - 1$.