la quête du Graal (s10e10)

C'est trivial : il suffit de compter le nombre total de chevrons dans les 3 adresses, et puis on multiplie 6 fois ce nombre de chevrons en en retirant un à chaque fois :

14 × 13 × 12 × 11 × 10 × 9 = 2 162 160 possibilités

Bon, si on voulait faire ça rigoureusement, on noterait :

$$A_{14}^6 = \frac{14!}{(14-6)!} = 14 \times 13 \times 12 \times 11 \times 10 \times 9$$

C'est une méthode très directe, des arrangements, comme on dit dans le jargon.

En analysant la provenance stricte des sous-ensembles uniques de 6 symboles (en tenant compte du fait que certains symboles comptent simultanément pour plusieurs planètes à cause des intersections), on obtient :

• Motif $(4, 1, 1)$ : 9 combinaisons uniques de 6 symboles.
• Motif $(3, 2, 1)$ : 132 combinaisons uniques de 6 symboles.
• Motif $(2, 2, 2)$ : 54 combinaisons uniques de 6 symboles.

Soit un sous-total de 195 combinaisons pour ces trois motifs théoriques simples.

À cause des intersections ($C \cap S = \{$ $\}$, $C \cap V = \{$ , $\}$, $S \cap V = \{$ $\}$), le fait de choisir un symbole partagé augmente immédiatement le score d'une seconde planète. La majorité des tirages tombe donc naturellement dans ces motifs dits « dégradés » :

• Motif $(3, 3, 2)$ : 591 combinaisons.
• Motif $(3, 2, 2)$ : 492 combinaisons.
• Motif $(4, 3, 2)$ : 296 combinaisons.
• Motif $(4, 3, 1)$ : 284 combinaisons.
• Autres motifs complexes : 1 145 combinaisons.

Les motifs à forte intersection représentent l'écrasante majorité des tirages possibles !

En effectuant la somme de tous les sous-ensembles uniques de 6 symboles obtenus pour l'intégralité des motifs possibles, on trouve exactement 3 003 combinaisons (ce qui correspond exactement au coefficient binomial $\binom{14}{6} = \frac{14!}{6!(14-6)!}$).

Sachant que chaque combinaison de 6 symboles génère $6! = 720$ permutations d'adresses, le nombre total d'adresses ordonnées à tester sur la Porte des Étoiles est de :

3 003 × 720 = 2 162 160

Mon cher Général, c'est de la logique pure et dure basée sur le théorème des tiroirs et l'analyse des unions d'ensembles.

Chaque planète ne comporte que 6 symboles. Supposons par l'absurde que nous puissions former une adresse de 6 symboles distincts sans utiliser aucun symbole d'une des planètes, par exemple Vagonbrei ($V$).

1. L'adresse devrait être formée uniquement avec des symboles de $Castiana \cup Sahal$.
2. L'union $C \cup S$ contient 11 symboles au total. Mais parmi ces 11 symboles, 3 d'entre eux (, , ) appartiennent aussi à Vagonbrei.
3. Les symboles de $C \cup S$ strictement absents de Vagonbrei sont seulement au nombre de 8.
4. Or, si l'on tente de construire une adresse de 6 symboles dans ces 11 symboles, il est mathématiquement impossible d'éviter les symboles d'intersection de Vagonbrei dès qu'on essaie de respecter la répartition des exclusifs.

En réalité, le réservoir global ne contient que 14 symboles. Tout tirage de 6 symboles distincts parmi 14 implique nécessairement qu'au moins un symbole appartienne à Castiana, au moins un à Sahal, et au moins un à Vagonbrei.

Conclusion pour le SGC :

• Le vrai coup de génie de Vala, c'est de nous avoir permis de restreindre la recherche aux 14 symboles de ces 3 planètes. Cela nous fait passer de $A_{38}^6 = 1\ 987\ 690\ 320$ adresses (presque 2 milliards !) à seulement $A_{14}^6 = 2\ 162\ 160$ adresses. Elle vient d'éliminer 99,89 % de la galaxie.
• En revanche, sa précision sur le fait que l'adresse contient « un mélange des trois mondes » n'apporte aucune réduction supplémentaire : tout tirage de 6 symboles dans ce pool de 14 valide déjà cette condition de manière automatique. Le total final à explorer reste donc de 2 162 160 adresses.