Du blé sur un échiquier

Dans un royaume très lointain, le roi voulut un beau jour récompenser son plus valeureux soldat. Il le fit donc venir dans son château et lui dit:

Mon brave guerrier, tu as toujours défendu ce royaume vaillamment et j’aimerais te récompenser largement. Je peux te couvrir d’or si tu le souhaites. Je peux te donner des tonnes de bijoux si cela est ta volonté. Dis-moi ce que tu veux et tu seras exaucé sur-le-champ.

Le soldat répondit très sobrement:

Ô roi, si tu veux me récompenser, offre-moi un échiquier sur lequel tu disposeras quelques grains de blé.

Le roi, légèrement interloqué, répliqua:

Cette requête est étrange, mais je reconnais bien là ton sens du sacrifice et ta légendaire modestie. Combien de grains de blé veux-tu qu’on dispose sur cet échiquier ?

Le soldat répondit:

Sur chaque case de cet échiquier, tu placeras un certain nombre de grains de blé en suivant les trois règles que je vais t’énoncer…

Avant de poursuivre, nous allons mettre en place quelques notations qui nous seront utiles pour comprendre les règles du soldat. Chaque case de l’échiquier sera repérée par ses coordonnées comme sur le schéma ci-dessous:

Nous noterons $A(m,n)$ le nombre de grains de blé posés sur la case de coordonnées $(m,n)$ .

Règle n°1: la première colonne

Ô roi, pour remplir la première colonne, tu commenceras par poser un grain de blé sur la première case, puis deux grains de blé sur la deuxième case, puis trois grains de blé sur la troisième case, etc.

Voici donc ce qu’on obtient:

En termes mathématiques, cela se note: $\boxed{A(0,n)=n+1}$ .

Règle n°2: la première ligne

Ô roi, pour remplir chaque case de la première ligne, tu mettras autant de grains de blé qu’il y en a dans la case située en haut à sa gauche.

Le schéma de remplissage de la première ligne est donc le suivant:

En termes mathématiques, cela se note $\boxed{A(m,0)=A(m-1,1)}$ .

Nous pouvons déjà en déduire le nombre de grains de blé sur la case $(1,0)$ :

Règle n°3: une case quelconque

Ô roi, pour remplir une case quelconque, tu commenceras par noter le nombre $n$ de grains de blés situés dans la case juste en dessous, puis tu prendras le nombre de grains de blé situés dans la colonne juste à gauche à la hauteur $n$ .

Pour bien comprendre cette règle, nous allons en donner plusieurs exemples. Commençons par la case $(1,1)$ (voir schéma ci-dessous; c’est la case avec le point d’interrogation). La case située en dessous contient 2 grains de blé, donc on va regarder la case située dans la colonne juste à gauche, à l’ordonnée 2. Sur cette case, il y avait 3 grains de blé donc, nous mettrons aussi 3 grains de blé sur la case $(1,1)$ .

Donc, $A(1,1)=3$ .

En termes mathématiques, la règle n°3 signifie $\boxed{A(m,n)=A(m-1,A(m,n-1))}$ .

Voici d’autres exemples:

A(1,2)=4

A(1,3)=5

A(2,1)=5. La case A(2,0) a été remplie à l’aide de la règle 2.

A(2,2)=7

Remarque: parfois, il faudra remplir une colonne au-delà de la hauteur de l’échiquier pour pouvoir remplir certaines cases de la colonne suivante. Par exemple:

Vous pouvez vous amuser à remplir cet échiquier à la main en suivant la méthode que je viens de décrire !

Encore plus de blé

Après avoir énoncé ces trois règles, le soldat dit:

La seule chose que je vous demande mon seigneur, c’est simplement de me donner autant de grains de blé qu’il y en a sur la case (4,2).

Entendant cela, le roi se retrouva fort embarrassé car il n’était pas capable de calculer le nombre de grains de blé qu’il devait donner à son soldat. Il décida donc d’envoyer des centaines de lettres manuscrites aux meilleurs mathématiciens du royaume. Malheureusement, aucun d’entre eux ne voulut résoudre ce problème, car tous considéraient qu’il s’agissait d’un vulgaire calcul indigne de leurs capacités. Ne sachant plus que faire, le roi sortit son smartphone dernier cri et, dans un anachronisme assumé, m’envoya un mail pour me demander de poster la solution sur mon blog.

Voilà comment je me suis retrouvé à poster cet article (histoire véridique ! Ça s’invente pas ce genre de choses…). Va falloir étudier ce problème maintenant. J’ai commencé les calculs sans vous, voici ce que j’ai obtenu:

La méthode informatique

La première idée qu’on peut avoir pour trouver le nombre de grains de blé sur la case (4,2) serait d’écrire un petit programme informatique qui calculerait les termes de cette suite double $A(m,n)$ par récurrence à l’aide des trois règles que nous avons décrites:

$A(m,n) = \begin{cases} n+1 & \text{ si } m=0\\ A(m-1,1) & \text{ si } n=0\\ A(m-1,A(m,n-1)) & \text{ sinon }\\ \end{cases}$

Le programme récursif n’est pas très dur à écrire, et voici ce qu’il donnerait en Python:

def A(m,n):
    if m==0:
        return n+1
    elif n==0:
        return A(m-1,1)
    else:
        return A(m-1,A(m,n))

Les premiers termes de la suite étant relativement petits, on peut penser que cela ne devrait pas poser trop de problème à un ordinateur pour calculer $A(4,2)$ avec ce programme. Mais avant de lancer ledit programme, essayons de comprendre les étapes qu’il suivra pour le calcul des termes de cette suite, en étudiant l’exemple du calcul de $A(1,2)$ :

$\begin{array}{cclr} A(1,2) &= & A(0, A(1,1)) & \text{Regle 3} \\ & = & A(0, A(0,A(1,0))) & \text{Regle 3}\\ & = & A(0, A(0, A(0,1))) & \text{Regle 2}\\ & = & A(0, A(0, 2)) & \text{Regle 1}\\ & = & A(0,3) & \text{Regle 1}\\ & = & 4 & \text{Regle 1} \end{array}$

On constate que c’est un calcul qui s’apparente à une simple promenade de santé. Pour nous en assurer, voyons voir ce qui se passe pour d’autres valeurs de $m$ et $n$ . Mais, pour ne pas avoir à écrire à la main à chaque fois toutes ces étapes, j’ai écrit un petit programme en Python qui affiche toutes les étapes du calcul de $A(m,n)$ dans un fichier texte, puis qui renvoie la valeur de $A(m,n)$ . Le programme se trouve ici. Et voici par exemple ci-dessous le fichier texte généré pour le calcul de $A(3,4)$ :

Calcul de A(3,4)

Comme vous le constatez dans ce fichier, le nombre d’étapes commence à être dangereusement important (environ 10307). Pour le fun (on s’amuse comme on peut), j’ai lancé le calcul de $A(3,6)$ ce qui (au bout d’une bonne minute !) a généré un fichier texte de 180Mo, composé de 273043 lignes (la limite de caractères par lignes dans un fichier texte tout simple étant de 1024… et certaines égalités tiennent sur au moins deux lignes) ! Si vous voulez mettre à mal un ordinateur, lancez le calcul de $A(4,2)$ et le fichier texte remplira le disque dur largement avant d’avoir pu calculer ce nombre… Voilà un bel exemple de virus d’origine mathématique !

La méthode mathématique

Nous voyons donc que la méthode informatique ne nous sera d’aucune aide ici car il semblerait que les nombres en jeu soient très grands. Il va donc falloir ruser un peu ! Si on reprend notre échiquier, et qu’on regarde la 4ème colonne, on constate quand même un certain modèle suivi par les nombres:

Vous avez trouvé ? Eh oui, ces nombres forment presque la suite des puissances de 2 sauf qu’elles sont diminuées de 3 à chaque fois. Pour prouver cela rigoureusement, nous allons montrer par récurrence que pour tout entier naturel $n$ , $A(3,n)= 2^{n+3} - 3$ .
Auparavant, on peut remarquer facilement en observant la 3ème colonne que pour tout $n$ , $A(2,n)=2n+3$ (il faudrait le montrer par récurrence là-aussi mais admettons-le…). Nous sommes prêts pour la preuve:

Si $n=0$ alors:
$\begin{array}{ccl} A(3,0) & =& A(2,1)\\ & = & 2 \times 1 +3 \\ & =& 5 \\ & = & 2^{0+3}-3\\ \end{array}$
Si on suppose que $A(3,n)= 2^{n+3} - 3$ alors:
$A(3,n+1)= A(2,A(3,n)) = A(2,2^{n+3}-3) = 2 \times( 2^{n+3} - 3) + 3 = 2^{n+4} - 3$
Donc, $A(3,n+1) = 2^{(n+1) + 3} - 3$ , ce qui prouve la propriété au rang suivant !

Sachant cela, nous pouvons à présent calculer facilement les nombres $A(4,0)$ et $A(4,1)$ puis en déduire $A(4,2)$ . Tout d’abord, la règle n°2 nous dit que

$A(4,0)= A(3,1) = 2^{1+3} - 3 = 13$

Ensuite, la règle n°3 nous dit que

$A(4,1)= A(3,A(4,0)) = A(3,13) = 2^{13 + 3} - 3 = 65533$ .

Nous pouvons enfin calculer le nombre de grains de blé à poser sur la case $(4,2)$ :

$A(4,2) = A(3,A(4,1)) = A(3,65533) = 2^{65533+3} - 3$

Donc, il faudrait poser $A(4,2) = 2^{65536} - 3$ grains de blé sur la case $(4,2)$ pour satisfaire la demande du soldat.

Ordre de grandeur

Le nombre $2^{65536}-3$ est grand, mais grand à quel point ? Essayons d’en donner un ordre de grandeur. On a $\log(2^{65536}) = 65536 \times \log(2) \simeq 19728,3$ . Or, $10^{19728,3} = 10^{19728} \times 10^{0,3}$ . Comme $10^{0,3} \simeq 2$ , on a donc

$A(4,2) \simeq 2 \times 10^{19728}$

Rien que ça. Sachant qu’il n’y a qu’environ $10^{80}$ atomes dans l’univers, vous vous rendez compte que le nombre de grains de blé à poser sur la case $(4,2)$ est scandaleusement élevé.

Et si on allait plus loin et qu’on regardait $A(4,3)$ ? Combien de grains de blé mettrions-nous sur la case $(4,3)$ ? Le calcul est le même que tout à l’heure:

$\begin{array}{ccl} A(4,3) & = & A(3,A(4,2)) \\ & = & A(3, 2^{65536} - 3)\\ & = & 2^{2^{65536}-3 + 3} - 3 \end{array}$

D’où, $A(4,3) = 2^{2^{65536}} -3 \simeq 10^{6 \times 10^{19727}}$ ! Du délire total.Le nombre $A(4,3)$ est par exemple largement supérieur au nombre total d’objets possibles qu’on peut former avec les atomes de l’univers, qui est de $2^{10^{80}}$ (nombre de parties d’un ensemble à $10^{80}$ éléments).

On se rend compte qu’il y a eu, entre la quatrième colonne et la cinquième colonne, une explosion de la valeur des nombres de grains de blé. La suite $A(m,n)$ est donc particulièrement étonnante, et si vous me demandiez quel est le nombre de grains de blé qu’il faudrait poser sur la dernière case de l’échiquier, je vous dirai que le nombre $A(7,7)$ est tellement gigantesque, tellement énorme, tellement immense (CMB), qu’il est même impossible de le concevoir mentalement.

Epilogue

Après avoir calculé le nombre de grains de blé à poser sur la case (4,2), j’envoyai un message au roi pour lui signifier qu’il devrait se procurer environ $2 \times 10^{19728}$ grains de blé pour pouvoir exaucer le souhait de son soldat. Le roi me répondit en me disant que tout compte fait, il lui offrirait un stylo-plume gravé à son nom accompagné d’une petite carte musicale personnalisée, et que cela ferait largement l’affaire.

Notes:

1) L’histoire de cet article s’inspire de la légende bien connue de ce roi, qui découvrant le jeu d’échecs, demanda à la personne qui le lui fit connaître ce qu’elle souhaitait comme cadeau. Cette personne lui dit de déposer un grain de blé sur la première case, puis deux grains sur la deuxième case, puis quatre grains sur la troisième case, etc. en doublant le nombre de grains à chaque fois. Un simple calcul de la somme des termes d’une suite géométrique montre que le nombre total de grains de blé sur l’échiquier est de $2^{64}-1$ . Il faudrait remplir de blé environ $2^{65472}$ échiquiers différents par cette méthode pour obtenir autant de grains de blé ce que nous en avions obtenu avec la seule case $(4,2)$ !

2) Pour information, cette suite que nous avons étudiée porte un nom: elle s’appelle la fonction d’Ackermann et a été découverte dans les années 1920 !

3) La valeur exacte de $A(4,2)$ se trouve ici… un nombre à 19729 chiffres !

4) Et pour finir, une petite vidéo où le calcul de la fonction d’Ackermann provoque un dépassement de mémoire tampon.

9 commentaires pour Du blé sur un échiquier

Pierre Lecomte dit :

26 mars 2014 à 23 h 35 min

C’est une amusante fonction, c’est bien de l’avoir illustrée, merci!

Elle joue un rôle en calculabilité, en établissant une hiérarchie au sein des fonctions primitives récursives. Elle est calculable, car récursive, mais pas primitive récursive. De plus, toute fonction primitive récursive d’une variable, disons f, est majorée par une des fonctions partielles de A : il existe M tel que f(n)<A(M,n) pour tout n. (Si ma mémoire est bonne — ce pourrait être A(n,M), mais je pense que ce n'est pas le cas; je n'ai pas mes notes de cours sous la main ici, chez moi, et cela fait bien dix ans que je n'ai plus enseigné cette matière, désolé; je regarderai peut-être demain, une fois dans mon bureau, ce qu'il en est). Le fait de disposer d'une telle fonction est important en calculabilité, entre autre en relation avec la thèse de Church-Turing.

J'aimeJ'aime

Réponse
- blogdemaths dit :
  
  27 mars 2014 à 0 h 13 min
  
  Merci beaucoup Pierre pour ces éclaircissements ! (Je parierais sur A(M,n) à l’intuition :D)
  
  J'aimeJ'aime
  
  Réponse
forum poker dit :

2 avril 2014 à 15 h 29 min

Jolie illustration ! Même si la légende de Brahmane Sissa n’est qu’une légende (l’invention du jeu d’échecs serait en fait antérieure à cette époque).

J'aimeJ'aime

Réponse
Johnd154 dit :

28 avril 2014 à 17 h 27 min

I am so grateful for your blog article.Really thank you! Fantastic. egkkfdcdkdff

J'aimeJ'aime

Réponse
The Dude dit :

3 juillet 2014 à 3 h 43 min

Un peu de synchronicité ! Une nouvelle vidéo sur Computerphile, la chaîne soeur de Numberphile: http://youtu.be/i7sm9dzFtEI

Cela fait aussi référence au commentaire de Pierre. Les vidéos qui précèdent sur les fonctions récursives sont aussi intéressantes.

J'aimeJ'aime

Réponse
- blogdemaths dit :
  
  29 juillet 2014 à 12 h 27 min
  
  Merci pour ce lien vers l’excellente chaine Computerphile !
  
  J'aimeJ'aime
  
  Réponse
blogdemaths dit :

15 juin 2016 à 13 h 29 min

Ton blog est à la fois joli et intéressant.. Content de voir que d’autres blogs mathématiques voient le jour !

J'aimeJ'aime

Réponse
- Victor Sannier dit :
  
  15 juin 2016 à 13 h 40 min
  
  Merci infiniment ça me fait très plaisir surtout venant de toi 😀
  
  J'aimeJ'aime
  
  Réponse
Gui-Boulet dit :

23 août 2017 à 16 h 58 min

Et le CMB, personne n’en parle ? Plus c’est gros, plus ça passe =)

J'aimeJ'aime

Réponse