56Powers

Solution of Problem 56.1.

1. The grains double from square to square starting at $1 = 2^0$: square $k$ holds $2^{k-1}$ grains (Definition 56.1). Square $64$ holds $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$: always one less than the next power of $2$ ($2$, $4$, $8$, $16$, $32$). Conjecture: $S_n = 2^n - 1$.

3. Doubling every term of $S_n$ shifts each power up by one ($2 \times 2^{k} = 2^{k+1}$):

Subtracting the first line from the second, every term from $2$ to $2^{n-1}$ appears in both and cancels:

4. The total is $S_{64} = 2^{64} - 1$ grains. A sixty-fifth square would hold $2^{64}$ grains: the whole board carries exactly one grain fewer than that single square would.

5. The first half holds $S_{32} = 2^{32} - 1$ grains. The whole board holds $2^{64} - 1$, so the second half holds

(factor out $2^{32}$, using $2^{32} \times 2^{32} = 2^{64}$, Theorem 56.3): exactly $2^{32}$ times the first half.

6. By the exponent rules, $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Since $2^{10} = 1024 > 10^3$,

7. More than $1.6 \times 10^{19}$ grains at $5 \times 10^{-2}$ g each:

Dividing by $10^6$ g per tonne: more than $8 \times 10^{11}$ tonnes — eight hundred billion tonnes.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$: the king promised at least a thousand years of today’s entire world harvest. (The legend says his advisers told him as much.)

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$. So the smallest exponent is $n = 20$: twenty doublings pass the million.

10. The pay on day $n$ is $2^{n-1}$ cents (day 1: $2^0 = 1$). Now

So the daily pay first exceeds $10^8$ cents when $n - 1 = 27$: on day $28$.

11. $21 = 16 + 4 + 1$: weights $16$, $4$ and $1$ g. $27 = 16 + 8 + 2 + 1$: weights $16$, $8$, $2$ and $1$ g.

12. By question 3, the weights $1, 2, 4, 8$ together weigh $S_4 = 2^4 - 1 = 15$ g. So without the $16$ g weight the merchant cannot pass $15$ g: any target of $16$ g or more must use it. And a target of $15$ g or less must not use it, since the $16$ g weight alone already exceeds the target. The choice of the largest weight is therefore forced. What remains is a target of at most $15$ g to be formed with $1, 2, 4, 8$ — and the same argument repeats: $8$ is forced (used if the remaining target is $\geq 8$, unused otherwise, because $1 + 2 + 4 = 7$), then $4$ (because $1 + 2 = 3$), then $2$, then $1$.

13. Following the forced choices, the remaining target after each stage is at most the total of the remaining weights, so the process ends with remainder $0$: every target from $1$ to $31$ is reached. And since every choice along the way was forced, no other selection of weights can reach the same target: the writing of each number from $1$ to $31$ as a sum of distinct powers of $2$ exists and is unique.

14. The six weights total $S_6 = 2^6 - 1 = 63$ g, and the same forced-choice argument covers every target from $1$ to $63$ g. For $45$: the target is $\geq 32$, so use $32$; remains $13 < 16$, so skip $16$; use $8$ (remains $5$), use $4$ (remains $1$), skip $2$, use $1$:

15. Choosing a $0$ or a $1$ on each of the $64$ squares amounts to choosing which powers $2^0, 2^1, \dots, 2^{63}$ to include in a sum — exactly the merchant’s weighing with $64$ weights. The smallest storable number is $0$ (all squares at $0$); the largest is the sum of all the powers, which is the king’s total: $S_{64} = 2^{64} - 1$ (Part I). By the forced-choice argument, every whole number in between is reached exactly once: a $64$-bit machine stores precisely the whole numbers from $0$ to $2^{64} - 1$.