Quentin L. Meunier
Associate Professor in Computer Science at Sorbonne Université
Dobble
The Dobble is a game composed of cards on which are drawn 8 symbols. These cards verify the following property: 2 cards taken randomly in the game share exactly one symbol in common. The person who presented me this challenge used these terms: "What is the maximum possible card number in the game?"
The first thing to notice is that the maximal number of possible cards only depends on the number of symbols on the card, provided there are enough distinct symbols. The number of symbols on the card thus determines the number of distinct symbols and the number of cards.
We can then notice that each symbol appears in a number of cards equal to the number of symbols on one card, what involves that there are as many cards as distinct symbols.
If we note C = number of cards, S = number of symbols on one card and D = number of distinct symbols, we have:
C = D = S * (S - 1) + 1
Besides, I thought I had found a formula which gives the explicit content of the cards, but I realized that it only works if S - 1 is a prime number. This formula is the following (Card[k][i] refers to the ith symbol of the kth card):
The values of the S first cards are trivially defined by:
Card[k][i] = 0 if i = 0
Card[k][i] = k × (s − 1) + i if i ≠ 0
The values for the following cards are defined by:
Carte[k][i] = s + (i − 1) × (s − 1) + ((k − s) / (s − 1) × (i − 1) + (k − 1) % (s − 1)) % (s − 1)
Here is a program implementing this formula for an arbitrary number of symbols (with a limit set to 15):