Quentin L. Meunier
Maitre de conférence en informatique à Sorbonne Université
Dobble
Le Dobble est un jeu composé de cartes, sur lesquelles figurent 8 symboles. Ces cartes vérifient la propriété que 2 cartes prises au hasard dans le jeu partagent exactement un symbole en commun. La personne qui m'a posé le défi l'a posé en ces termes : "Combien de cartes au maximum peut-il y avoir dans le jeu ?" (pour que le problème soit intéressant, il faut exclure la solution où toutes les cartes comportent le même symbole commun)
La première chose à remarquer est que le nombre maximal de cartes possibles ne dépend que du nombre de symboles sur la carte, du moment qu'il y a assez de symboles différents. Le nombre de symboles sur la carte détermine donc le nombre de symboles différents et le nombre de cartes.
On peut ensuite remarquer que chaque symbole apparait dans un nombre de cartes égal au nombre de symboles sur une carte, ce qui implique donc qu'il y a autant de cartes que de symboles différents.
Si on pose C = nombre de cartes, S = nombre de symboles sur une cartes et D = nombre de symboles différents, on a donc :
C = D = S * (S - 1) + 1
Par ailleurs, je pensais avoir trouvé une formule qui explicite les cartes pour un nombre S donné quelconque, mais j'ai remarqué qu'elle ne marchait que si S - 1 est un nombre premier (i.e. pour S = 3, 4, 6, 8, 12, etc.). Cette formule est la suivante (Carte[k][i] représente le i-ème symbole sur la k-ième carte) :
Les valeurs des S premières cartes sont définies trivialement par :
Carte[k][i] = 0 si i = 0
Carte[k][i] = k × (s − 1) + i si i ≠ 0
Les valeurs des cartes suivantes sont définies par :
Carte[k][i] = s + (i − 1) × (s − 1) + ((k − s) / (s − 1) × (i − 1) + (k − 1) % (s − 1)) % (s − 1)
Voici un programme implémentant cette formule pour un nombre arbitraire de symboles (avec une limite fixée à 15) :