Solution au problème de mars 2011

Le problème:

Ce mois-ci, notre problème rend hommage à Jorge Luis Borges, auteur de La Bibliothèque de Babel et Le Livre de Sable. L'Encyclopédie Cabbaliste de l'Alphabet est un recueil de sept volumes énumérant toutes les permutations de l'alphabet, en ordre alphabétique. Puisque ces permutations sont très nombreuses, les volumes sont très gros, et l'écriture y est minuscule. Chaque volume contient exactement la septième partie de la liste des permutations. Ainsi, en examinant à la loupe la première page du premier volume, vous verrez tout en haut la toute première permutation, soit abcdefghijklmnopqrstuvwxyz suivie de abcdefghijklmnopqrstuvwxzy. Le problème: Quelle est la dernière permutation de ce premier volume?   Nous avons reçu les solutions correctes de Luigi Bernardini (Italie) Daniel Bitin Lou Cairoli (États Unis) Bernard Collignon (France) Mei-Hui Fang (Autriche) Philippe Fondanaiche (France) Gruian Cornel (Roumanie) Tom Holens (Manitoba) Benoît Humbert (France) Ile Ilijevski (Macédoine) Kipp Johnson (États Unis) Wolfgang Kais (Allemagne) Antek Łączkowski (Pologne) Matthew Lim (États Unis) Patrick J. LoPresti (États Unis) M.C. Juan Mir Pieras (Espagne) John T. Robinson (USA) Dustin Sawatzky Mathias Schenker (Suisse) Albert Stadler (Suisse) Hakan Summakoğlu (Turquie) Paul Voyer (France)

La solution:

La solution la plus simple est celle de Kipp Johnson qui a commandé en ligne l'Encyclopédie Cabbaliste de l'Alphabet, et a ouvert le premier volume à la dernière page.Par contre, selon les calculs de Lou Cairoli, cette encyclopédie comporte $4.03 \times 10^{26}$ permutations soit plus que le nombre de grains de sable sur terre(moins de fewer that $10^{24}$ selon http://www.newton.dep.anl.gov/askasci/ast99/ast99215.htm. On ne peut donc employer cette approche à moins d'avoir l'espace suffisant. Nous reproduisons plutôt la solution de Humbert:

"Il existe, en tout, 26! permutations de l'alphabet. Le premier des sept volumes en contient 1/7×26!.

1/7×26! = 26/7×25!

= 3×25! + 5/7×25!

= 3×25! + 125/7×24!

= 3×25! + 17×24! + 6/7×24!

= 3×25! + 17×24! + 144/7×23!

= 3×25! + 17×24! + 20×23! + 4/7×23!

= 3×25! + 17×24! + 20×23! + 92/7×22!

= 3×25! + 17×24! + 20×23! + 13×22! + 1/7×22!

= 3×25! + 17×24! + 20×23! + 13×22! + 22/7×21!

= 3×25! + 17×24! + 20×23! + 13×22! + 3×21! + 1/7×21!

= 3×25! + 17×24! + 20×23! + 13×22! + 3×21! + 3×20!

Dans ce volume, les 25! premières permutations commencent par a, les 25! suivantes par b, et ainsi de suite.

3×25! < 1/7×26! ≤ 4×25!

La première lettre de la dernière permutation du premier volume est donc la quatrième lettre de l'alphabet : d.

De même :

- La seconde lettre de la permutation est la dix-huitième dans l'alphabet privé de d, c'est-à-dire la dix-neuvième de l'alphabet complet : s ;

- La troisième est la vingt-et-unième de l'alphabet privé de d et s, c'est-à-dire la vingt-troisième de l'alphabet complet : w ;

- La quatrième est la quatorzième de l'alphabet privé de d,s et w, c'est-à-dire la quinzième de l'alphabet complet : o ;

- La cinquième est la quatrième de l'alphabet privé de d,o,s et w, c'est-à-dire la cinquième de l'alphabet complet : e ;

Attention : 2×20! < 3×20! ≤ 3×20!

La sixième lettre de la permutation est donc la troisième de l'alphabet privé de d,e,o,s et w, c'est-à-dire la troisième tout court : c. Et les lettres suivantes sont les lettres restantes de l'alphabet, dans l'ordre anti-alphabétique.

La dernière permutation du premier volume est finalement :

dswoeczyxvutrqpnmlkjihgfba''

Commentaires. Plusieurs de nos correspondants ont noté la ressemblance entre la solution à notre problème et la conversion d'un nombre de la base 10 à une autre base. En effet, tout entier positif $m$ inférieur à $(n+1)!$ a une représentation unique
$$m = a_nn! + a_{n-1}(n-1)! + \dots + a_1(1!) + a_0(0!)\;,$$
où $a_k$ est un entier, $0 \le a_k \le k$, $k = 0, \dots , n$. On abbrévie cette représentation comme suit
$$m = a_na_{n-1}\dots a_10_!,$$
la représentation de $m$ en numérotation factorielle. (L'indice factoriel est inspiré de la représentation d'un nombre dans une base quelconque.) Par exemple, $13 = 2010_! = 2\cdot3! + 0\cdot 2! + 1\cdot 1! + 0 \cdot 0!$. Le pangramme de Renaud Lavigne, qui comprend toutes les lettres de l'alphabet, est la phrase

Clown au QG : rythmez dix kJ BF, SVP.

(avec QG : quartier général, kJ : kilojoules, BF : basse fréquence et SVP : s'il vous plaît)

Il correspond à la permutation portant le numéro

$$2[10][12][19][11]0[15][11]4[11][14][11]472[10]1283200110_!.$$

La permutation de notre problème est $26!/7 = 3[17][20][13]3300\dots0_!$, se terminant avec $20$ zéros. On trouve des détails sur la numérotation factorielle (en anglais) dans l'article Wikipédia http://en.wikipedia.org/wiki/Factorial_number_system. Ceux qui lisent l'anglais apprécieront aussi la référence Willi am Goldbloom Block, The Unimaginable Mathematics of Borges’ Library of Babel, Oxford University Press, 2008, qui nous a été communiquée par Cairoli.