Soit un jeu de n cartes où chacune possède m symboles.
Nous nous plaçons d’abord dans le cas où il y a m+1 cartes avec le même symbole (S1). Les autres symboles de ces m+1 cartes sont tous différents.
Supposons qu’il existe une carte qui ne contient pas S1, elle doit alors posséder un symbole de chacune des m+1 cartes, donc elle doit avoir m+1 symboles.
C’est impossible, donc si il y a m+1 cartes avec S1, toutes les cartes possèdent S1 et donc tous les autres symboles sont différents. On a donc en tout x = 1 + (m-1) * n symboles.
Pour notre cas de 55 cartes à 8 symboles, il faudrait donc avoir x = 386 symboles différents !
Nous nous plaçons maintenant dans le cas où il n’y a au maximum m cartes qui contiennent le même symbole.
Nous pouvons construire un jeu avec m carte qui contiennent S1. Ces m cartes nécessitent 1 + (m-1)*m symboles différents.
Nous construisons ensuite la suite de ce jeu, sans ajouter de nouveaux symboles, en prenant comme premier symbole des m-1 cartes suivantes un des symboles de la première carte (S2) puis en plaçant une permutation de la matrice (m-1) x (m-1) des symboles des cartes 2 à m (sans le premier S1).
On recommence l’opération avec les m-1 symboles de la première carte, ce qui nous fait en tout 1 + (m-1)*m cartes, soit autant que de symboles (ce qui est logique puisque chaque symbole se trouve sur m cartes et que chaque carte contient m symboles).
Donc le nombre maximal de cartes possible est N = 1 + (m-1)*m. C’est le jeu optimisé à m symboles par carte, qui possède x = N = 1+ (m-1) * m symboles différents.
Pour m=8, ce nombre maximal est donc N = 57.
Le jeu de carte de scaff60 ne possédant que n=55 cartes, c’est donc possible que ce soit un jeu de 57 auquel on a retiré 2 cartes, ce qui fait que 15 symboles n’apparaissent que 7 fois et 1 seulement 6 fois (celui en commun des 2 cartes retirées), et tous les autres 8 fois.
Montrons maintenant que l’on ne peut pas avoir de solution avec moins de 57 symboles pour un jeu de 55 cartes.
On va en fait montrer, d’une manière générale, que si le jeu possède plus de cartes que N – m, alors N symboles sont nécessaires
Soit donc un jeu de n cartes où : N – m = m²-2m+1 < n < N
Supposons (Hyp1) que le nombre de symboles est x < N = 1 + (m-1)*m
Supposons (Hyp 2) que chaque symbole n’apparaisse que sur m-1 cartes au maximum, on aurait au maximum x * (m-1) symboles sur l’ensemble des cartes, c’est à dire au maximum x * (m-1)/m cartes, soit n <= x *(m-1)/m < (1 + (m-1) *m) * (m-1)/m = 1 – 1/m + (m-1)²
Donc, n < m² - 2m + 1, c’est impossible, donc (Hyp2) est fausse : donc au moins un symbole (S1) apparaît m fois.
Sur ces m cartes où S1 apparaît, il y a 1 + m*(m-1) symboles différents, ce qui contredit (Hyp1), donc le nombre de symboles différents est >= N, donc au minimum x=N.
Pour un jeu qui possède N – m cartes, ou moins, on peut retirer m cartes du jeu optimisé avec le même symbole et donc x = N-1 symboles différents sont suffisants.
Si le jeu possède N – m – (m-1) ou moins, on peut retirer du jeu précédent m-1 cartes avec le même symbole (la dernière carte portant ce symbole ayant été enlevée précédemment).
Etc… (jusqu’à N – m – (m-1) - … -1)
Pour n<=m+1, le nombre de symboles nécessaires est la partie supérieure droite de la matrice suivante (exemple avec n=8), dont le dénombrement est aisé.
S01 S02 S03 S04 S05 S06 S07 S08
S01 S09 S10 S11 S12 S13 S14 S15
S02 S09 S16 S17 S18 S19 S20 S21
S03 S10 S16 etc…
…
S08 S15 S21 S26 S30 S33 S35 S36
Pour m+1 < n <= (m²-3m)/2+1… j’ai pas encore trouvé de formule !
En conclusion :
pour m et n donnés, on a les valeurs de x suivantes :
Si m²-m+1 < n, alors x = 1+(m-1)*n
Si m²-m+1-(i+1)m+i(i+1)/2 < n <= m²-m+1 -im+(i-1)i/2 , alors x = m²-m+1-i, pour 0<= i <= m-1
Si n<=m+1, x=n*m – (n-1)n/2
Accueil
