Dobble


Sept. 13, 2018

Introduction

I've never actually played Dobble (also called Spot It!), but we bought it for our son's friend and I thought it sounded intriguing. There are various ways to play, but they all use a special deck in which each card has a number of symbols (8 in the standard pack, 6 in the kids pack).

Dobble cards

Photo: Bunch of Dobble cards, by msaari CC BY-NC 3.0

The cards are designed such that:

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.

Both my partner and I wondered how you could design a deck that works this 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?

After playing around for a while, I realised that, contrary to my expectation, there's probably no simple formula. 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 B B C C A

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.

A B A C A D

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 .

A B C B C D

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.

A B C C D E

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$

A A B C D E

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$

A A B B C D D E F

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}$

1 2 3 4 5 6 7 8 9 10

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$.

A A B B C C D D E E F F

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$.

ABC ADE BDF CEF ABC ADE BDF CEF A B C D E F A B C D E F

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:

  1. Create an $n \times n$ table.
  2. Block out the diagonal.
  3. Fill in the lower triangle of the table with different symbols.
  4. 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.

A B C A D E A F G

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.

A B C A D E A F G A H I B D F H
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.

B D F B E G C D G C E F

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).

A A A B B B C C C D D D E E E F F F G G G

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$).

A A A A B B B B C C C C D D D D E E E E F F F F G G G G H H H H I I I I J J J J K K K K L L L L M M M M
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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

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:

  1. Every pair of distinct points determines exactly one line.
  2. 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.

A B C

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.

A B C D A B C D E A B C D E F

Projective planes

We can make the rules more stringent by considering projective planes. These are linear spaces where:

  1. Every pair of distinct lines meet in exactly one point.
  2. 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.

A B C D E F G

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.

Matrix for projective plane of 13 points

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.

A B C D A E F G B E H I

With nine symbols we do now have space for three cards of four symbols.

A B C D A E F G B E H I

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.

ABCD AEFG BEHI CFHJ DGIJ ABCD AEFG BEHI CFHJ DGIJ A B C D E F G H I J A B C D E F G H I J

We can keep going, plotting the results on a graph.

Total symbols (n) Maximum number of cards (k) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 5 9 13 17 21

Dobble plus one

The graph consists of a series of ever larger peaks, each of which occurs at a Dobble number. The peaks increase linearly because at the Dobble numbers $k = n$. After 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}$.

Total symbols (n) Mean symbol repeats (r) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 2 3 4 5

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.

{{ symbolCount[symbol] || 0 }} {{ symbol }} {{ index + 1}} {{ symbol }} ×

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.

Leave a comment

cancel reply