Grands nombres palindromes

Dans son article sur les nombres palindromes du Pour la Science n°480, Jean-Paul Delahaye nous lance un défi de voir si l'on pouvait repousser les limites du plus grand nombre palindrome construit à partir de N chiffres et des 4 opérations + - * /.

Un nombre palindrome est un nombre « miroir », il a la même valeur lu de gauche à droite ou de droite à gauche : 9, 727, 12321, ...

Les records précédents, listés sur le site de Erich Friedman (Math and Computer Science Department at Stetson University, Floride) étaient les suivants, trouvés par Erich Friedman :

Nb chiffres	Formule	Plus grand palindrome
12	7×8×8×8×8×9 × (4×7×7×9×9−3)	4095995904
13	7×7×7×7×7×8 × (7×7×7×8×8×8+6)	23613431632
14	9×9×9×9×9×9 × (9×9+2) × (4×7×7×8−6)	68899199886
15	7×7×7×7×8×8×8×8×8 × (2+9) × (9×9×9+3)	633498894336

En cherchant en brute force on est vite limité : pour passer de N à N+1, on ajoute un chiffre et un opérateur en plus ce qui multiplie par 9×4=36 la complexité. Pour 15 chiffres cela ferait 9¹⁵×4¹⁴=55268479930183339474944 soit près de 10²³ possibilités à parcourir...

Une autre technique consiste à penser chaque résultat comme la combinaison de 2 résultats, chacuns pouvant être eux-mêmes le résultat de 2 résultats, etc.
Notons n_i un nombre combinaison de i chiffres; 72 est un n₂ car 8×9=72, 82 est un n₃ car 9×9+1=82. Par exemple pour N=13 on a le produit d'un n₆ et un n₇ : le n₆ A=7×7×7×7×7×8, et le n₇ B=(7×7×7×8×8×8+6). A et B étant eux mêmes composés de 2 éléments n_x : A est le produit de deux n₃ (7×8×8)×(8×8×9) et B est le produit d'un n₅ et d'un n₁ :(4×7×7×9×9)−(3). Chacun peu à nouveau se décomposer jusqu'à des n₁.
Donc en stockant tous les n₂, on peut les réutiliser pour calculer tous les n₃, etc.
Remarque : dans notre cas on cherche le palindrome le plus grand, donc on ignorera la division, car tout n_i / x est un n_j avec j<i.
Voici le nombre de n_i , comparé au nombre de combinaisons possibles :

i	Nombre de ni	Nombre de combinaisons ci de i chiffres (9i×3i−1)	%age ni / ci
2	30	243	12.3456789012%
3	155	6561	2.3624447493%
4	739	177147	0.4171676630%
5	3665	4782969	0.0766260455%
6	16807	129140163	0.0130145414%
7	76117	3486784401	0.0021830142%
8	363831	94143178827	0.0003864656%
9	1764050	2541865828329	0.0000006939%
10	8331952	68630377364883	0.0000001214%

On peut alors parcourir l'arbre de recherche considérablement rétréci, et finir par trouver en 2h de calcul tous les n₁₃ (et donc le plus grand palindrome parmi ceux-ci), puis les n₁₄, et les n₁₅ en quelque 8h de calcul sur un simple PC. Voici donc les nouveaux résultats que j'ai obtenu, courant 2017 :

Nb chiffres	Formule	Plus grand palindrome	Date
13	9×9×9×9×9×9 × (6×7×7×7×7×9−8)	68899199886	10/2017
14	(9×9×9×9×9×5+4) × (8×8×8×8×9×9−5)	97955055979	10/2017
15	((5×9×9×9×9×9−7)×7) × ((8×9×9×9×9−7)×8)	867685586768	10/2017
16	((7×7×7×7×7×8−5)×4) × (9×8×8×8×8×8×8×7)	8881871781888	10/2017
17	(8×8×8×8×8×(9×9×7+2)) × ((9×9×9×9×8×7+6)×9)	61655222255616	10/2017
18	(8×8×(8×8×8×8×8×7+1)) × (9×(9×9×9×9×9×9×9−1))	631931242139136	10/2017
19	(6×8×8×8×8×8×8×9×9+5) × (9×8×8×(7×8×8×8×9+7))	2367573333757632	10/2017
20	(8×8×8×8×8×9×9×9×9+3) × (9×9×7×(6×9×9×9×9×9+8))	43189347374398134	10/2017
21	((8×8×8×8×8×9×9×9+5)×7×9) × (2×8×8×9×9×9×9×9×9+3)	86925062526052968	10/2017
22	(6×9×9×9×9×9×9×9×9+3)×9 × ((7×7×7×7×9×9×9+7)×7×9×9)	2306950757570596032	10/2017
23	((8×8×8×9×9×9×9×9×9×9-1)×9) × ((7×9×9-2)×9×9×9×9×9×9-3)	6617798452548977166	11/2017
24	((7×9×9×9×9×9×9−8)×9×9×9×9) × (((6×8×8×8×8×8+5)×8×9×9+1)×9)	9539972462642799359	11/2017

Le programme décrit donne non pas la formule mais la valeur du palindrome et seulement la dernière opération qui y a mené (une multiplication entre un n_i et un n_j). Il faut donc retrouver la décomposition de chacun. Un autre programme parcourt les possibilités qui y mènent.

La porte est ouverte pour d'autres records...

Compléxité des jeux de domino, belote et autres

Est-ce que dans une vie on peut rejouer plusieurs fois une même partie de domino ou de cartes (bridge, belote...) ?

Pour répondre essayons de déterminer quel est le nombre de distributions des cartes (des fiches, des pions, ...) différentes possibles entre les joueurs.

Petits rappels

Pour faire ces calculs nous avons besoin de 2 outils : les factorielles et les combinaisons.
Factorielle n - notée n! - est le produit 1*2*3*...*(n-1)*n. Par exemple 6!=1*2*3*4*5*6=.
Les combinaisons donnent le nombre de tirages différents de k éléments parmi n, et est appelé C(k, n). Il vaut n!/k!(n-k)!.
Enfin s'il y a p1 possibilités pour un choix c1, et p2 pour un choix c2, le nombre total de possibilités est leur produit p1*p2.

Application à notre jeu

Dans le cas de la distribution de n cartes entre les joueurs, le nombre de distributions différentes est donc le produit des p_j=C(k, n_j) de chaque joueur j. S'il y a 32 cartes réparties entre 4 joueurs :

• le premier joueur tire 8 cartes parmi 32 : p1=C(8, 32)
• le deuxième joueur tire 8 cartes parmi les 24 restantes : p2=C(8,24)
• le troisième tire 8 cartes parmi 16 : p3=C(8,16)
• et enfin le 4ème prend les 8 cartes restantes : p4=C(8, 8) (qui est égal à 1).

Le nombre total de combinaisons est donc :
p1 * p2 * p3 * p4 = C(8,32) * C(8,24) * C(8,16) * C(8,8) = .
À raison de 20 parties par jour il faudrait pour jouer toutes ces parties !

Conclusion

NON, il est très improbable de rejouer 2 fois une même partie !!!! Par ailleurs ceci est juste le nombre de distributions de départ ! Il faut tenir compte de ce que va jouer chaque joueur pour calculer le nombre de parties différentes, ceci sera l'objet d'un autre billet.

Autres jeux

jeu	Nb joueurs	Nb cartes par joueurs	Nb cartes	Nb distributions
Belote Bridge Domino Domino cubain (9)

Compléments

Factorielles

7! = . Essayer une autre valeur : n= n!=---
En savoir plus (wikipedia)

Combinaisons

C(4,8) : . Essayer une autre valeur : k= n= C(k,n)=---
En savoir plus (wikipedia)

Distributions

Nombres de distributions pour un jeu de belote (4 joueurs, 32 cartes):
Nombres de distributions pour un jeu de domino (4 joueurs, 28 fiches):
Nombres de distributions pour un jeu avec joueurs, et cartes/fiches C(k,n)=---