L’app Sort Puzzle distribue une nouvelle grille à chaque partie. Au total, combien de grilles de départ existe-t-il ? Comptons par le calcul.

★1 : 63 063 000 arrangements

★1 est une grille de 16 éléments (4 couleurs, 4 éléments chacune) répartis dans 4 tubes de 4 places.

123456

Si l’on range les 16 éléments dans l’ordre, du bas du tube de gauche vers la droite, le nombre d’arrangements est celui des permutations de 16 éléments, divisé par le nombre d’échanges entre éléments de même couleur.

16! ÷ (4! × 4! × 4! × 4!) = 20 922 789 888 000 ÷ 331 776 = 63 063 000 arrangements

(16! vaut 16×15×…×1 et 4! vaut 4×3×2×1 = 24.)

De plus, l’app choisit 4 couleurs parmi 10, soit 210 choix de couleurs. Si l’on distingue aussi les couleurs, cela donne 63 063 000 × 210 = 13 243 230 000 grilles (environ 13,2 milliards).

Les chiffres pour chaque difficulté

Si l’on laisse de côté le choix des couleurs et que l’on compare seulement les arrangements, le nombre explose à mesure que les couleurs augmentent.

DifficultéArrangements de couleursPart de donnes équitables
★1 (4 couleurs)environ 63,06 millions80,42 %
★2 (6 couleurs)environ 3,2×10¹⁸87,07 %
★3 (8 couleurs)environ 2,4×10²⁴90,36 %
★4 (10 couleurs)environ 1,3×10³⁴92,33 %
★5 (9 couleurs)environ 1,4×10³²91,46 %

10¹⁸ est un 1 suivi de 18 zéros (un trillion). Le nombre pour ★4 est environ 1,3 fois un 1 suivi de 34 zéros.

Environ 8 à 9 donnes sur 10 sont équitables

L’app n’utilise pas les donnes où un tube contient 3 éléments de même couleur ou plus à la suite (un tube presque trié dès le départ est ennuyeux). La « part de donnes équitables » du tableau est la proportion de donnes sans ce genre de tube. Je l’ai comptée exactement, en dénombrant tube après tube le nombre de couleurs possibles.

Pour ★1, sur 63 063 000 arrangements, 50 717 088 (80,42 %) sont des donnes équitables. Plus il y a de couleurs, moins il est probable qu’une même couleur se suive, donc la part de donnes équitables augmente.

Les grilles de la taille de ★1 sont toutes solubles

J’ai examiné toutes les donnes équitables de ★1 pour vérifier si elles sont solubles. En considérant comme identiques deux donnes qui ne diffèrent que par l’ordre des tubes ou par un simple échange de couleurs, on obtient 89 675 types de donnes.

J’ai ajouté deux tubes vides à ces 89 675 types et essayé tous les coups, un par un : toutes étaient solubles. Les 111 383 types, en incluant les donnes non équitables (avec un tube de 3 éléments de même couleur ou plus à la suite), étaient eux aussi tous solubles.

Autrement dit, avec 4 couleurs et 2 tubes vides, quelle que soit la façon de distribuer, la grille est toujours soluble. En ★1, l’app n’a jamais à écarter une donne insoluble.

Pour ★2 à ★4, où il y a plus de couleurs, on ne peut pas tout vérifier, mais sur 400 à 500 donnes examinées pour chacune, toutes étaient solubles. En revanche, en ★5, avec un seul tube vide, la plupart des donnes sont insolubles (Comment on crée des grilles toujours solubles).