56Las potencias

Solución de Problema 56.1.

1. Los granos se duplican de casilla en casilla empezando en $1 = 2^0$: la casilla $k$ tiene $2^{k-1}$ granos (Definición 56.1). La casilla $64$ tiene $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$: siempre uno menos que la potencia de $2$ siguiente ($2$, $4$, $8$, $16$, $32$). Conjetura: $S_n = 2^n - 1$.

3. Duplicar todos los términos de $S_n$ sube cada potencia en uno ($2 \times 2^{k} = 2^{k+1}$):

Restando la primera línea de la segunda, todos los términos de $2$ a $2^{n-1}$ aparecen en las dos y se cancelan:

4. El total es $S_{64} = 2^{64} - 1$ granos. Una casilla sexagésima quinta tendría $2^{64}$ granos: el tablero entero lleva exactamente un grano menos que esa sola casilla.

5. La primera mitad tiene $S_{32} = 2^{32} - 1$ granos. El tablero entero tiene $2^{64} - 1$, así que la segunda mitad tiene

(saca factor común $2^{32}$, usando $2^{32} \times 2^{32} = 2^{64}$, Teorema 56.3): exactamente $2^{32}$ veces la primera mitad.

6. Por las reglas de los exponentes, $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Since $2^{10} = 1024 > 10^3$,

7. Más de $1.6 \times 10^{19}$ granos a $5 \times 10^{-2}$ g cada uno:

Dividiendo entre $10^6$ g por tonelada: más de $8 \times 10^{11}$ toneladas — ochocientos mil millones de toneladas.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$: el rey prometió al menos mil años de la cosecha mundial entera de hoy. (Cuenta la leyenda que sus consejeros se lo dijeron.)

9. $2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524\,288 < 10^6$, while $2^{20} = \left(2^{10}\right)^2 = 1024^2 = 1\,048\,576 > 10^6$. Así que el menor exponente es $n = 20$: veinte duplicaciones pasan del millón.

10. La paga del día $n$ es $2^{n-1}$ céntimos (día 1: $2^0 = 1$). Ahora bien,

Así que la paga diaria supera por primera vez $10^8$ céntimos cuando $n - 1 = 27$: el día $28$.

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

12. Por la pregunta 3, las pesas $1, 2, 4, 8$ juntas pesan $S_4 = 2^4 - 1 = 15$ g. Así que, sin la pesa de $16$ g, la comerciante no puede pasar de $15$ g: cualquier objetivo de $16$ g o más tiene que usarla. Y un objetivo de $15$ g o menos no debe usarla, ya que la pesa de $16$ g sola ya supera el objetivo. La elección de la pesa mayor está, por tanto, forzada. Lo que queda es un objetivo de como mucho $15$ g que hay que formar con $1, 2, 4, 8$ — y el mismo argumento se repite: el $8$ está forzado (se usa si el objetivo restante es $\geq 8$ y no se usa si no, porque $1 + 2 + 4 = 7$), después el $4$ (porque $1 + 2 = 3$), después el $2$ y después el $1$.

13. Siguiendo las elecciones forzadas, el objetivo que queda después de cada etapa es como mucho el total de las pesas restantes, así que el proceso termina con resto $0$: se alcanzan todos los objetivos de $1$ a $31$. Y, como todas las elecciones del camino estaban forzadas, ninguna otra selección de pesas puede alcanzar el mismo objetivo: la escritura de cada número de $1$ a $31$ como suma de potencias de $2$ distintas existe y es única.

14. Las seis pesas suman $S_6 = 2^6 - 1 = 63$ g, y el mismo argumento de elección forzada cubre todos los objetivos de $1$ a $63$ g. Para $45$: el objetivo es $\geq 32$, así que usa $32$; quedan $13 < 16$, así que salta el $16$; usa $8$ (quedan $5$), usa $4$ (queda $1$), salta el $2$ y usa $1$:

15. Elegir un $0$ o un $1$ en cada una de las $64$ casillas equivale a elegir qué potencias $2^0, 2^1, \dots, 2^{63}$ se incluyen en una suma — exactamente la pesada de la comerciante con $64$ pesas. El número almacenable menor es $0$ (todas las casillas a $0$); el mayor es la suma de todas las potencias, que es el total del rey: $S_{64} = 2^{64} - 1$ (Parte I). Por el argumento de la elección forzada, todo número entero intermedio se alcanza exactamente una vez: una máquina de $64$ bits guarda precisamente los números enteros de $0$ a $2^{64} - 1$.