Introduction
Dobble (also called Spot It!), is a card game that uses special circular cards, each with a number (8 in the standard pack, 6 in the kids pack) of symbols or image. There are various ways to play, but they all the games involve finding which symbol is common to two cards. The cards are designed so that any two cards will always have one symbol in common.
This got us wondering: how you could design a deck that way?
More formally:
- Given $n$ different symbols, how many cards can you make, and how many symbols should be on each card?
- Given $s$ symbols per card, how many cards can you make and how many different symbols do you need?
- If you want to make $k$ cards, how many symbols do you need on each card, and how many in total?
The requirements for the cards are:
Requirement 1: every card has exactly one symbol in common with every other card.
Requirement 2: each card has the same number of symbols.
Requirement 3: no symbol appears more than once on a given card.
After playing around for a while, I realised that, contrary to my expectation, there's probably no simple formula for the number of symbols and cards. Instead, there is quite a lot of room for exploration. A couple of weeks later, someone asked one of these exact questions on a Facebook group called Actually good math problems (it's a closed group, so you have to join to see the post).
No answer was given on the group, but someone posted links (included at the end of this post) to articles on pairwise balanced design and incidence geometry, so it seems there is real mathematical value in some of these concepts. This article however, is about my more empirical exploration.
Starting simple
To get a handle on the problem, I started playing about, starting with the simplest situation and gradually building up. I found it easiest to vary the total number of symbols, which I'll call $n$. I recommend trying to create some decks with small values of $n$.
With one symbol, e.g. $\{A\}$, you can have one card: a card with the symbol $A$. Technically, given the requirements above, you could have infinite cards, each with just an $A$ on it, so we'll add a requirement.
Requirement 4: each card must be unique.
With two symbols, $\{A, B\}$, you can still only have one card: one with the symbols $A$ and $B$ on it (which I'll write as $AB$). Technically we could instead have just a card with an $A$ or just a card with a $B$, but we'll add another requirement.
Requirement 5: given $n$ symbols, each symbol must appear on at least one card.
Smallest non-trivial deck
With three symbols, $\{A, B, C\}$, we have something more interesting: three cards, each with two symbols: $AB$, $AC$ and $BC$. You can even arrange them a bit like dominos, joined by their common symbols.
Is there something special about the number three?
A trivial general solution
With four symbols, you could have three cards: $AB$, $AC$ and $AD$. However, since Dobble involve spotting the common symbols between cards, this would make the game trivial (because the common symbol would always be the same). It also makes the problem less interesting, because we can can always create $n - 1$ cards this way. So we'll add final(ish) requirement.
Requirement 6: there should not be one symbol common to all cards.
I worded the requirement so we can still have decks of one card. With this requirement our only solution is a deck of one card: $ABCD$. We need more than two symbols per card because with two symbols per card, three cards most you can have. I'll explain this later, but if you play about with the symbols for a while this should soon become clear. It relates to the fact that with three cards, each card has two symbols and each symbol appears on two cards.
The pigeonhole principle
For $n = 4$, we need to have at least three symbols per card. But with three symbols per card there are six positions in which to put four symbols, so we can't avoid an overlap of two symbols .
This is an example of the pigeonhole principle, which is an obvious-sounding idea that is surprisingly useful in many contexts. It states that:
If $n$ items are put into $m$ containers, with $n > m$, then at least one container must contain more than one item.
With five symbols we now have "space" for three symbols per card with an overlap of one, for example: $ABC$ and $CDE$. Technically, this fails to meet requirement 6, since $C$ is common to all two cards, so I decided to alter requirement 6 slightly. This isn't really necessary, but I think it makes the graphs slightly nicer later.
Requirement 6 (amended): there should not be one symbol common to all cards if $n > 2$.
Triangular numbers
With five symbols, three symbols per card works because the first card provides three symbols, whilst the second provides two additional symbols and one to overlap. More generally, if we have $s$ symbols per card, then we can make two cards when the number of symbols is:
$\qquad k = 2, n = s + (s - 1) = 2s - 1$
With six symbols, we can go one better. The first card gives us three symbols, the second adds two more, and the third add another. In general, if we have $s$ symbols per card, then we will be able to make three cards when the number of symbols is:
$\qquad k = 3, n = s + (s - 1) + (s - 2) = 3s - 3$
We can generalise further to get a value for any $k$. Every time we add a card, we add $s$ symbols minus one symbol to match each existing card, which gives us:
$\qquad n = sk - (1 + 2 + \text{...} + (k - 1))$
The sum of the numbers $1 + 2 + \text{...} + k$ are the triangular numbers, so called because they are the number of items required to build triangles of different sizes. They are generated by the formula:
$\qquad T(k) = \dfrac{k(k + 1)}{2}$
Substituting in the equation for triangular numbers, we get:
$ \qquad\begin{align} n &= sk - T(\color{blue}{k - 1}) \\ n &= sk - \frac{\color{blue}{(k - 1)}(\color{blue}{(k - 1)} + 1)}{2} \\ n &= sk - \frac{k(k - 1)}{2} \end{align} $
We might expect that if $n$ is the triangular number $T(s)$, then we could have $s$ cards, e.g. three cards with three symbols each. In fact, we can go one better. When we have $s$ cards, $s - 1$ symbols are matched on each card. In other words, each card has exactly one unmatched symbol. We can therefore create a new card using these $s$ unmatched symbols ($CEF$ in the diagram). If we sum the new symbols added by each card, we get $3 + 2 + 1 + 0 = 6$.
We can verify the number of cards algebraically by rearranging the above formula to find an equation for $k$ when $n$ is a triangular number.
$ \qquad\begin{align} T(s) &= sk - T(k - 1) \\ \frac{s(s + 1)}{2} &= sk - \frac{k(k - 1)}{2} \\ s^2 + s &= 2sk - k^2 + k \\ k^2 + k(-2s - 1) + s^2 +s &= 0 \\ \end{align} $
Which is a quadratic with solutions with coefficients $a = 1$, $b = -2s - 1$, $c = s^2 +s$. If you solve for $k$, you get $k = \dfrac{2s + 1 \pm 1}{2}$. In other words $k = s$ and $k = s + 1$. So when $n$ is a triangular number you can have $s$ cards, but you can also have $s + 1$ cards.
Conclusion: With $s$ symbols per card we can create $s + 1$ cards using $\dfrac{s(s+1)}{2}$ symbols in total.
Note that this does require that $s > 1$ because whilst one card does have one unmatched symbol, we can't add a second card with that unmatched symbol because we'd end up with two cards the same. It does work with $s = 2$ giving $k = 3$ and $n = 3$, which was the previous best deck.
Making matrices
Another way to understand why triangular numbers work well is to make a matrix of cards, showing which symbols they share.
We can line up each card in rows and columns, then for each cell in the table, we write the one symbol that is common to the cards for that row and that column. The diagonal is blocked out since we don't compare cards to themselves. This table forms two triangles of symbols, one above and one below the diagonal. We only need to look at one triangle since comparing, say, card $ABC$ to card $ADE$ is the same as comparing card $ADE$ to card $ABC$.
With this arrangement each row and each column spells out the symbols on that card. In addition, each triangle above or below the diagonal, contains each symbols once. This gives us a method to create $n$ cards:
- Create an $n \times n$ table.
- Block out the diagonal.
- Fill in the lower triangle of the table with different symbols.
- Read along the columns and rows to get the symbols for each card.
The problem with this method is that requires a lot of symbols. The real Dobble deck has 55 cards, which would require having 54 symbols on each card and a total of 1485 different symbols. Because we put each symbol in the table once each symbol is only used twice. Can we be more efficient by having symbols appear on more than two cards?
Maximising symbol repetition
So far, when creating cards we have chosen to match symbols that have not yet been matched. But what if we make the first three cards all share the same symbol. The first thing to notice is that with $s = 3$, when now need $n$ to be at least seven symbols: one repeated symbol and three lots of two symbols.
Can we add a fourth card matching the same symbol? This would require $n = 9$. But, in order to meet requirement 5 we need at least one card that doesn't have an $A$. And that means that for the fifth card we need to match symbols on four cards, where those cards have no symbol in common with each other except $A$, and we can only pick three symbols. In other words, with $s = 3$, each symbol can only be repeated three times.
Conclusion: If each card has $s$ symbols, then each symbol can occur at most $s$ times.
So instead of repeating $A$ again, we create two more cards with a $B$ and two more cards with a $C$ to give a total of seven cards. In doing so, we also end up repeating the remain symbols, so each one occurs exactly three times. This also gets us our biggest deck yet - almost double what we got with six symbols.
If we use the triangular number method to get seven cards, we need 21 symbols, each appearing on two cards. This new arrangement uses a third of the number of symbols by having each symbol appear on three cards.
Dobble numbers
Seven symbols is the sweet spot for $s = 3$ because it allows each symbol to appear the maximum three times. You view this as splitting the symbols into the first one, $A$, and then three groups of two, $\{BC\}, \{DE\}, \{FG\}$. Alternatively you can view this as the first card, followed by three groups of two cards in which the symbols on the first card ($A$, $B$ and $C$) are repeated twice each.
The image shows the seven cards in rows, with the seven symbols in columns. If you move your mouse over a card, all its symbols are highlighted on all cards (so exactly one symbol should be highlighted on each other card).
In general, with $s$ symbols per card, the most symbols, $n$, and also the most number of cards we can have, $k$, is one plus $s$ lots of $s - 1$.
$n = k = 1 + s(s - 1) = s^2 - s + 1$
I call these Dobble numbers, $D(s)$. The first few Dobble numbers are 1, 3, 7, 13, and 21. They are all odd, since $s(s - 1)$ is always even.
Here's the example with 13 symbols, leading to 13 cards with four symbols per card. The lines show how I split the cards and symbols into groups ($ABCD$, $EFG$, $HIJ$ and $KLM$).
Conclusion: If each card has $s$ symbols, then we can make $k = s^2 - s + 1$ cards. Each symbol will appear $s$ times and the number of different symbols will equal $k$.
I'm not 100% sure that you can always build a deck of this size, but pretty sure you can't build one larger. Either way, we can get an equation for $s$ in terms of $k$, using the quadratic formula, with $a = 1$, $b = -1$ and $c = 1 - k$.
Conclusion: For $k$ cards, the minimum number of symbols per card is $s = \left\lfloor \dfrac{1 + \sqrt{4k - 3}}{2} \right\rfloor$.
Where $\lfloor n \rfloor$ means "round $n$ down to the nearest whole number.
What I call the Dobble numbers are called sequence A002061 in the Online Encyclopedia of Integer Sequences. The page gives a long list of properties for this sequence. One interesting property which appears completely unrelated, is that this sequence of numbers occurs along the diagonal if you write the positive integer in a grid, starting in the middle and spiralling out.
An unexpected sidestep into geometry
So far, with the possible except of the spiral above, this has been a problem of combinatorics which seems logical given the nature of the problem. However, the discussion on Facebook suggested a geometric interpretation. The terminology is a little intimidating, but it's basically describing the same problem using points and lines.
Incidence geometry and linear spaces
We can represent each symbol as a point and each card as a line. Points that lie on a line then represent symbols on a card. Now the problem is one of incidence geometry: the study of which points lie on which lines. A linear space is an incidence structure where:
- Every pair of distinct points determines exactly one line.
- Every line contains at least two distinct points.
Rule 1 corresponds to the requirement that no two cards are the same. Rule 2 corresponds to the fact that we want cards to have at least two symbols. The requirements for Dobble are more stringent, but this is enough for now.
The simplest non-trivial linear space consists of three points and corresponds nicely to how we arranged the three cards like dominos. If you mouse over a point, the two lines it's connected to are highlighted; if you mouse over a line, the two points that lie on it are highlighted.
You can build similar diagrams with four, five and six points. The fact that line $BDF$ is a circle in the diagram with six points is a side-effect of drawing the diagram in 2D. In terms of the geometry, there is no difference between any of the lines.
Projective planes
We can make the rules more stringent by considering projective planes. These are linear spaces where:
- Every pair of distinct lines meet in exactly one point.
- There exist four points, no three of which lie on the same line.
The first rule corresponds to the key rule for Dobble, namely every card should share at least one symbol with every other card. The second rule is there to rule out situations where all the points lie on the same line.
The most famous projective plane is called the Fano plane, which is famous enough that I'd seen before (in Professor Stewart's incredible numbers). The plane consists of seven lines and seven points. Every line goes through three points and every point lies on three lines. It has all sorts of interesting properties and symmetries.
Projective planes all consists of $n^2 + n + 1$ points where $n$ is the number of points ($s$) on a line minus 1. If you plug $s - 1$ into this you get the number of points is $s^2 - s + 1$, just like the rule I discovered. On the Wikipedia page on projective planes there is a matrix representing a projective plane with 13 points which looks just like to the diagram I made for 13 cards of four symbols. Unfortunately, I don't think there is a nice diagram for arranging 13 points and 13 lines.
Larger decks
Getting back to the empirical approach, we can continue to increase the number of symbols to see if any more patterns emerge.
With eight symbols, we have a similar situations as with four symbols. We need more than three symbols per card because three symbols are maxed out by seven cards. But with four symbols, two cards don't cover all the symbols (requirement 5), and with three cards, there's not enough symbols. With five or more symbols, the overlap between two cards is too great.
With nine symbols we do now have space for three cards of four symbols.
With ten symbols we have the fifth triangular number, and so can get five cards of four symbols. Since this is a triangular number each symbol appears on exactly two cards.
We can keep going, plotting the results on a graph. Notice the series of peaks at the Dobble numbers, each one having $k = n$.
Dobble plus one
Following each Dobble number, when $n = D(s) + 1$, the value of $k$ crashes. For the first three "Dobble plus one" numbers ($2$, $4$ and $8$), the deck size is one. With 14 symbols we finally have enough symbols to scrape four cards together.
The numbers $2$, $4$ and $8$ are also powers of two. With 16 symbols, we have the first power of two, which is not a "Dobble plus one" number. With 16 symbols we can make six cards, which is a lot better than one. However we can also make six cards with with 15 symbols (a triangular number). This is the only example so far where increasing $n$ doesn't increase $k$ other than the "Dobble plus one" numbers. So it seems that it's hard to make decks when $n$ is a power of two.
Symbol repetition
Another interesting parameter to look at is the mean number of times each symbol appears in a deck, $r$. For example with nine symbols, we had the cards $ABCD$, $AEFG$ and $BEHI$. So $A$, $B$ and $E$ appear twice, while the remaining six symbols appear once. Therefore $r = \frac{3 \times 2 + 6 \times 1}{9} = \frac{4}{3}$.
Perhaps unsurprisingly, this graph has a similar shape to before since the more cards in a deck, the more each symbol is repeated. One small difference is that now there is a dip at $n = 16$ rather than a flat line. A more interesting trend becomes apparent when we look at values for which $r$ is an integer.
We already know when $n$ is a triangular number, $r = 2$, and when $n$ is the Dobble number, $D(s)$, $r = s$ ($21$ is both a triangular number and a Dobble number, but the Dobble number wins out since we want the largest deck). The first four powers of two, $1$, $2$, $4$ and $8$, all have one card, so $r = 1$.
Dobble minus one
There is one other type of number that has an integer value for $r$: the "Dobble minus one" numbers. When $n$ one less than a Dobble number, the number of repeats is one less than for that Dobble number, i.e if $n = D(s) - 1$, then $r = s - 1$.
- With $n = D(2) - 1 = 2$, $r = 1$
- With $n = D(3) - 1 = 6$, $r = 2$
- With $n = D(4) - 1 = 12$, $r = 3$
- With $n = D(5) - 1 = 20$, $r = 4$
This is just an empirical observation, based on these four (five if you include $D(1) - 1 = 0$) values. I don't have yet have any proof or any sense of the logic for why this might be the case (assuming the pattern holds).
The total number of symbols in a deck is equal to the number of symbols multiplied by the average number of repeats. So if this pattern does hold, the total number of symbols in these decks, $N$, is:
$\qquad \begin{align} N &= (D(s) - 1) \cdot (s - 1) \\ N &= (s^2 - s) \cdot (s - 1) \\ N &= s^3 - 2s^2 + s \end{align}$
The number of cards in a deck, $k$, is equal to the total number of symbols divided by the number of symbols per card:
$\qquad \begin{align} k &=\dfrac{N}{s} \\ k &=\dfrac{s^3 - 2s^2 + s}{s} \\ k &= s^2 - 2s + 1 \\ k &= (s - 1)^2 \end{align}$
Conjecture: If the number of symbols, $n$, is in the form $s(s - 1)$, then $k = (s - 1)^2$.e.g $n = 12 = 4 \times 3$, so $k = 3^2 = 9$
Finding large decks
Once the deck size gets into the teens, it becomes hard to be sure that you've found the best solution using pen and paper. So I built a tool to help me. It keeps track of which cards you've matched and stops you from adding symbols found on matched cards. This means a lot of the works is done for you and often only have to worry about picking the correct first symbol for each card.
Click on the letters to add or remove them from a card.
To find even larger decks I tried to write a program to find decks by brute force, trying all valid solutions. Sadly, I think it worked in $O(n!)$ time or worse, so by the time I reached $n = 12$ it was taking too long to run. There's probably a lot I could do to improve its efficiency, but I think I need a more clever strategy to get anything useful. I think that looking at the number of times each symbol is repeated as the deck is built might yield something, but I haven't worked out the specifics.
The actual game
The real game of Dobble has 55 cards with eight symbols on each card. The eighth Dobble number is $D(8) = 8^2 - 8 + 1 = 57$ so they could have had two more cards. I guess they decided 57 didn't seem like such a nice number. Presumably there are then 15 ($8 + 7$) symbols that appear only seven times. The Dobble Kids version has six symbols per card and "30 cards with more than 30 paper animals". More than 30 paper animals must refer to the fact that there are 31 ($D(6)$) different symbols.
Useful links
Here are various links I came across whilst researching this topic. I didn't really use any of them to write this article; I've mainly put them here so I can remember what I should read when I get the chance. I've noticed that a quite a lot of articles have since been written on the subject of Dobble, but none quite like this I think.
Comments (12)
Aaron McCann on 15 Mar 2019, 10:23 a.m.
Thanks for this Peter, it's something I've been rolling around in my head for ages. Only when tackling it with a pen & paper does it become clear there isn't a systematic solution.
One bit of advice: play Dobble, it's fantastic.
Sam on 11 May 2019, 4:17 p.m.
Thank you very much for doing the math to make dobble cards together with my kids with our own characteres !! I started thinking and my high school math was far too old...Internet is great :D Thank you again.
Rahulkumar on 26 Aug 2019, 4:21 p.m.
Thanks a lot Peter for detailed analysis. It helped me a lot to understand dobble better.
Charles on 4 Jan 2020, 4:35 p.m.
Thanks Peter for a really helpful explanation. Always wondered how it worked!
Simon Collins on 9 Jan 2020, 9:32 p.m.
I'm fascinated with stuff like this and after playing with my kids a Xmas I wondered how the maths of the game played out. Thanks for saving me weeks of scratching me head!
Adrian Leigh on 8 Feb 2020, 10:59 p.m.
Genius. The first time I played this with my kids, they were beating me as all I was thinking about was the maths involved. It seemed within my grasp and I was wrestling with it, but clearly it isn’t easy. Quite brilliant.
Neil Jones on 16 Feb 2020, 11:36 a.m.
Thanks for this! I was lying in bed this morning trying to think this through in my head (after playing Dobble with my daughter last night), but it was only when I put pen to paper I realised the solution wasn’t as mathematically straightforward as I thought it was going to be, particularly ensuring that all symbols were equally as likely to be the paired one.
Pavel Žáčik on 21 Feb 2020, 8:59 p.m.
Thank you. You saved me lots of time.
Scott on 9 Mar 2020, 3:37 a.m.
Thanks for the clear explanations and navigation of the thinking and repeated reasoning.
Were you able to find a set of cards that would have 11 symbols on each of 111 cards? What about 7 cards on 43 cards?
Kevin Rayment on 29 Mar 2020, 12:36 p.m.
I imagine that the reason they decided to have 55 rather than 57 cards is that once the cards are dealt and the face up card is removed this leaves 54 cards to be dealt rather than 56. 54 is of course exactly divisible by 2 and 3 (plus the much less useful 6, 9, 18 and 27) which are likely to be the most frequent number of players, whereas 56 is divisible by 2 and 4 but not 3 (plus the much less useful 7, 8, 14 and 28) so it does allow for 4 people, but this may be less frequently required than 3 [Benford's law may help suggest how more likely 2 players would be than 3?].
Of course, they could have supplied 57 and just have expect people to remove some cards each time which would assist if playing with 4. Based on this thinking, it may initially suggest a deck of traditional playing cards should have been created with 54 cards, which may have crossed the minds of anyone who has taken the 2 of clubs out when playing 3 player games. However, I struggle to imagine that 3 suits of 18 cards or 6 suits of 9 cards would work as well as the traditional design, although that may just be due to familiarity.
Lauri M on 13 Apr 2020, 10:37 a.m.
A small correction to your comment about the real dobble deck: there are 14 symbols that occur seven times and one that occurs only six times (the common symbol of the two missing cards). When playing the game, it is useful to know which of the symbols are these less probable ones. And even more interesting task is to determine which two cards are the missing ones.
Henrique Belo on 7 Oct 2020, 3:44 p.m.
Super cool. Thanks a lot for all the effort in understanding it and put it into such great article. Like everyone else here, I was wondering about this without grasping any kind of solution.