16 commentaires

feuilles de papier
La légende raconte qu’un jour, un Roi découvrit un tout nouveau jeu : le jeu d’échec. Pour remercier le sage qui inventa le jeu, le Roi lui proposa la récompense suivante : on plaça sur la première case de l’échiquier une pièce d’or. Sur la deuxième, on en place deux. Sur la troisième on en place quatre. Puis huit, puis seize et ainsi de suite en doublant le nombre de pièces à chaque fois jusqu’à la soixante-quatrième case. Le sage refusa l’offre dans un premier temps. Il préféra plutôt qu’on remplace les pièces d’or par des grains de blés.
Le Roi accepta, malgré ce qu’il pensait être comme une demande pleine d’humilité.

Il se trouve qu’en réalité l’inventeur du jeu amassa au total 18 446 744 073 709 551 615 grains de blé, soit environ 370 milliard de tonnes de blé (à raison de 50 grains par gramme). Ceci représente environ 1600 fois la production annuelle actuelle et mondiale de blé… Qui donc parlait d’humilité ?

Si on arrive à un nombre tellement monstrueux, c’est que le fait de doubler chaque valeur de case en case suit une évolution exponentielle : ça augmente, et ça augmente de plus en plus vite. Ici, l’exponentielle se fait en base 2 : on double (×2) à chaque case. Si bien qu’au bout de 64 cases, on a $2^0+2^1+2^2+2^3+\ldots+2^{63}$ grains de blé, et ça fait en effet beaucoup.

La leçon à retenir ici, c’est qu’il ne faut pas jouer avec les puissances et les exponentielles : vous perdrez toujours.

Un autre exemple, c’est l’exemple de la feuille de papier que vous pouvez faire chez vous : prenez une feuille de papier A4. Pliez-là en deux. Puis encore en deux. Puis encore en deux. Et ainsi de suite jusqu’à ce que ça soit impossible.
Combien de fois pouvez vous plier à la suite ? Pas plus de sept fois. Vous pouvez aussi essayer avec une feuille de journal ou tout autre affiche ou poster : vous n’atteindrez jamais dix pliages !

Si on ne peut pas plier beaucoup de fois, c’est parce que le nombre d’épaisseurs de papier double à chaque pliage. Au bout de la septième fois, vous aurez ainsi $2^7=128$ épaisseurs de papier à plier, soit le quart d’une ramette de papier et sur une toute petite surface.

Au passage, si vous étiez vraiment très fort et que vous pouviez plier 54 fois le papier, l’épaisseur du pliage dépasserait la distance Terre-Soleil d’environ 20% (sur la base d’un papier de 10 µm d’épaisseur).

image de Pascal Bovet

16 commentaires

gravatar
Le Hollandais Volant a dit :

@jambbon : oui, je sais, mais comme tu dis : une feuille de la taille d’un hangar c’est pas ce qu’on appelle communément « une feuille de papier ».

gravatar
ianux a dit :

Pour l'invention de l'échiquier, je connaissait une version qui parait plus simple : le roi propose à l'inventeur la récompense de son choix et celui-ci - connaissant son affaire - demanda une quantité de grains de blé doublée à chaque case et le roi, devant l'humilité apparente de ce choix, accepta sans broncher.

gravatar
Frodon1 a dit :

Avec une feuille de papier d'aluminium on peut dépasser les 7 plis ;)

gravatar
Migwel a dit :

Euh... La légende, ce n'est pas ça. Comme expliqué dans le lien Wiki que tu donnes :

Lorsque le sage Sissa, fils du Brahmine Dahir, lui présenta le jeu d'échecs, le souverain, enthousiaste, demanda à Sissa ce que celui-ci souhaitait en échange de ce cadeau extraordinaire. Humblement, Sissa demanda au prince de déposer un grain de riz sur la première case, deux sur la deuxième, quatre sur la troisième, et ainsi de suite pour remplir l'échiquier en doublant la quantité de grain à chaque case.

Si à la base, le roi lui proposait des pièces d'or sur chaque case, ce cher Sissa aurait eu tort de demander des grains de riz, une pièce d'or ayant plus de valeur qu'un grain de riz.

gravatar
Gee a dit :

L'exemple de l'échiquier est aussi vachement intéressant en terme de complexité, parce qu'il montre que ce type de problème est insoluble à notre échelle.

Mon prof d'algorithmique en école d'ing nous avait dit un truc genre « rien que pour compter les grains de blé, avec un ordinateur d'il y a 20, il aurait fallu un million d'années. Bon maintenant, avec les ordinateurs actuels, on peut le faire en un temps raisonnable. Mais il suffit de rajouter une ligne et une colonne, et on est repartis pour un million d'années... »

Tout le casse-tête de la complexité exponentielle...

gravatar
Matheod a dit :

Gee: Non vu qu'il y a des formules simples pour ça (somme d'une suite géométrique) :)

gravatar
Le Hollandais Volant a dit :

@Gee :
@Matheod : je serais plutôt de l’avis de Matheod. Surtout pour les puissances de 2 : en langage binaire c’est très simple :
$2^2 = 100_{(bin)}$
$2^3 = 1000_{(bin)}$
$2^{10} = 10000000000_{(bin)}$

Et l’addition de nombres en binaire (surtout des puissances de 2) est tout aussi simple :
$2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 1_{(bin)}+ 10_{(bin)} + 100_{(bin)} + 1000_{(bin)} + 10000_{(bin)} = 11111_{(bin)}$

Etc.

Le seul problème serait d’avoir des variables assez grandes pour contenir le $2^{81}$ d’une grille 9×9. Mais que je sache, il est possible d’aller très haut. Les formats long (unsigned?) double peuvent aller jusqu’à $2^{16384}$, ce qui est gigantesque.

https://en.wikipedia.org/wiki/Quadruple-precision_floating-point_format

Autrement je vois pas trop où es le problème.

gravatar
Gee a dit :

Oui, j'ai mal formulé le truc, je voulais dire pour « énumérer », pas pour compter (donc en gros, faire une boucle simple qui parcourt chaque grain de riz sans rien faire d'autre). Sinon oui, trouver la valeur du total, en soi, c'est trivial.

gravatar
Merveille AMO a dit :

Bonjour,
J'ai vraiment besoin d'aide pour un exercice :

Voici la consigne:
Vers l'an 600, en Inde, le roi, qui s'ennuie à la cour, demande qu'on lui invente un
jeu pour le distraire. Le sage Sissa invente alors le jeu d'échecs, ce qui ravit le roi.
Pour remercier Sissa, le roi lui demande de choisir sa récompense.
Le sage répond qu'il voudrait autant de grains nécessaires, pour remplir l'échiquier
de la façon suivante :
1 grain pour la première case ; 2 sur la deuxième ; 4 sur la troisième ; 8 sur la
quatrième ; … en doublant le nombre de grains jusqu'à la dernière case.
Le roi trouva cette demande bien modeste.


La production mondiale annuelle de blé est d'environ 660 millions de tonnes.
Un grain de blé pèse en moyenne 50 mg.

En considérant seulement les grains de blés posés sur la dernière case de l'échiquier, évaluer combien de
temps il faudrait aujourd'hui pour produire une telle quantité.
Vous présenterez votre démarche en faisant figurer toutes les pistes de recherche, même si elles nn'ont pas
abouti.


Merci d'avance :)

gravatar
Le Hollandais Volant a dit :

Il suffit de voir que :
– la case 1 contient 2^0 grains
– la case 2 contient 2^1 grains
– la case 3 contient 2^2 grains
– …
– la case n contient 2^(n−1) grains.

À partir de là, tu calcule :
– la masse de blé sur la dernière case (connaissant la masse d’un grain de blé)
– le nombre d’années qu’il faut pour produire ça (connaissant la production de blé en un an).
N’oublies pas de convertir les milligrammes en tonnes.

C’est tout.

gravatar
YOLO a dit :

y a pas 64 cases dans un jeu d'echec ???????

gravatar
Emily Smartiz a dit :

Par contre, dans:

a(0)+a(1)+a(2)+a(3)+...+a(63)=.....

Ce ne serai pas plutôt 64 au lieu de 63 vu qu'il y a 64 cases dans l'échiquier ?

gravatar
Le Hollandais Volant a dit :

@Emily Smartiz : nope, car la numérotation commence à 0 et non pas à 1.

La première case est la case a(0) ;
La deuxième case est la case a(1) ;
La troisième case est la case a(2) ;

La soixante-quatrième case est la case a(63) ;

Il y a bien 64 cases, mais on ne va donc que jusqu’à 63.

gravatar
EaSy_VoX a dit :

C'est marrant mais si on compte en binaire c'est beaucoup plus simple que les puissance vus que la première case compte 1 grain de riz en binaire 1=1 2=10 4=100 8=1000 jusqu'à 64 et ensuite tu convertis en décimal et voilà
ce qui donne 1000000000000000000000000000000000000000000000000000000000000000=9 223 372 036 854 775 808


Remarque : Votre commentaire sera visible après validation par le webmaster.