56Puissances

Solution de Problème 56.1.

1. Les grains doublent de case en case à partir de $1 = 2^0$ : la case $k$ porte $2^{k-1}$ grains (Définition 56.1). La case $64$ porte $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$ : toujours un de moins que la puissance de $2$ suivante ($2$, $4$, $8$, $16$, $32$). Conjecture : $S_n = 2^n - 1$.

3. Doubler chaque terme de $S_n$ décale chaque puissance d’un cran ($2 \times 2^{k} = 2^{k+1}$) :

En retranchant la première ligne de la seconde, tous les termes de $2$ à $2^{n-1}$ figurent dans les deux et se simplifient :

4. Le total vaut $S_{64} = 2^{64} - 1$ grains. Une soixante-cinquième case porterait $2^{64}$ grains : l’échiquier entier porte donc exactement un grain de moins que cette seule case.

5. La première moitié porte $S_{32} = 2^{32} - 1$ grains. L’échiquier entier en porte $2^{64} - 1$, donc la seconde moitié en porte

(en factorisant par $2^{32}$ et en utilisant $2^{32} \times 2^{32} = 2^{64}$, Théorème 56.3) : exactement $2^{32}$ fois la première moitié.

6. Par les règles sur les exposants, $2^{64} = 2^{4 + 60} = 2^4 \times \left(2^{10}\right)^6$. Comme $2^{10} = 1024 > 10^3$,

7. Plus de $1.6 \times 10^{19}$ grains à $5 \times 10^{-2}$ g chacun :

En divisant par $10^6$ g par tonne : plus de $8 \times 10^{11}$ tonnes — huit cents milliards de tonnes.

8. $\dfrac{8 \times 10^{11}}{8 \times 10^{8}} = 10^3$ : le roi a promis au moins mille ans de la récolte mondiale actuelle tout entière. (La légende raconte que ses conseillers le lui firent remarquer.)

9. $2^{19} = 2^9 \times 2^{10} = 512 \times 1024 = 524\,288 < 10^6$, tandis que $2^{20} = \left(2^{10}\right)^2 = 1024^2 = 1\,048\,576 > 10^6$. Le plus petit exposant est donc $n = 20$ : vingt doublements passent le million.

10. La paie du jour $n$ vaut $2^{n-1}$ centimes (jour 1 : $2^0 = 1$). Or

La paie journalière dépasse donc $10^8$ centimes pour la première fois lorsque $n - 1 = 27$ : le jour $28$.

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

12. D’après la question 3, les poids $1, 2, 4, 8$ réunis pèsent $S_4 = 2^4 - 1 = 15$ g. Sans le poids de $16$ g, la marchande ne peut donc pas dépasser $15$ g : toute cible de $16$ g ou plus doit l’utiliser. Et une cible de $15$ g ou moins ne doit pas l’utiliser, puisque le poids de $16$ g dépasse à lui seul la cible. Le choix du plus gros poids est donc forcé. Il reste alors une cible d’au plus $15$ g à former avec $1, 2, 4, 8$ — et le même argument se répète : $8$ est forcé (utilisé si la cible restante vaut $\geq 8$, écarté sinon, car $1 + 2 + 4 = 7$), puis $4$ (car $1 + 2 = 3$), puis $2$, puis $1$.

13. En suivant les choix forcés, la cible restante après chaque étape ne dépasse jamais le total des poids restants : le procédé s’achève donc sur un reste nul, et toute cible de $1$ à $31$ est atteinte. Et comme chaque choix en chemin était forcé, aucune autre sélection de poids ne peut atteindre la même cible : l’écriture de chaque nombre de $1$ à $31$ comme somme de puissances de $2$ distinctes existe et est unique.

14. Les six poids totalisent $S_6 = 2^6 - 1 = 63$ g, et le même argument de choix forcé couvre toutes les cibles de $1$ à $63$ g. Pour $45$ : la cible vaut $\geq 32$, on utilise donc $32$ ; il reste $13 < 16$, on écarte $16$ ; on utilise $8$ (il reste $5$), on utilise $4$ (il reste $1$), on écarte $2$, on utilise $1$ :

15. Choisir un $0$ ou un $1$ sur chacune des $64$ cases revient à choisir quelles puissances $2^0, 2^1, \dots, 2^{63}$ inclure dans une somme — exactement la pesée de la marchande avec $64$ poids. Le plus petit nombre stockable est $0$ (toutes les cases à $0$) ; le plus grand est la somme de toutes les puissances, c’est-à-dire le total du roi : $S_{64} = 2^{64} - 1$ (partie I). D’après l’argument des choix forcés, chaque entier intermédiaire est atteint exactement une fois : une machine sur $64$ bits stocke précisément les entiers de $0$ à $2^{64} - 1$.