Dobble Vision

Via http://www.dans-ma-tribu.fr/8-meilleurs-jeux-de-societe-pour-enfants/

My children got this game for Christmas. We haven’t played it yet. We got as far as me opening the tin and reading the rules, at which point I got distracted by the maths and forgot about the game.

So, the mathematical thing about Dobble is this:

  • It consists of 55 cards
  • Each card contains eight symbols (see image below)
  • Each card has exactly one — and only one — symbol in common with every other card in the pack
Via https://www.flickr.com/photos/lwr/8392145671

This fascinated me. According to the instructions, there were 50 symbols in total. I was instantly interested in the numbers: Why 50 symbols? Why 55 cards? Why eight symbols per card? But I was also interested in the concept: Maybe it’s just me, but I struggled to grasp how it would be possible to design a 55-strong pack such that every card would have one and only one symbol in common with every other card.

To get a handle on the maths, I decided to try and construct a pack, for myself, representing each new symbol as a number:

I reasoned that I could start with one source card, whose eight symbols would be represented by the numbers 1 to 8. After that, I would create eight new cards, each one of which contained one of the numbers 1 to 8. Given that each of the eight new cards could only have one thing in common with the source card, the other numbers had to be new numbers.

But in the process of adding the new numbers, I also made sure that each of the new cards could have one number in common with each of the other new cards. I hoped that if I continued in this vein I would spot a pattern. It was working great — I now had nine cards, and it looked like a pattern might be emerging. But as soon as I tried to add a tenth card, it all went awry.

I’m not going to spend too much time explaining this to be honest, because I realised later that it was utterly wrong-headed. It was hard to think about, and I don’t want you to worry your head trying to grasp it. Feel free to skip the next two paragraphs. But suffice to say that if you look at the rows numbered A2 to A8 on my scrap of paper above, you’ll see a diagonal pattern of pairs running top left to bottom right, where each row shares a number with the one below (you can see two 9s, then two 16s, then two 22s etc). This is all brilliant until you reach the row below A8, where the last number is 36.

I realised this was a problem when I decided to add another eight rows, again starting with the numbers 1 to 8, which would also each have one number in common with the original source card (A1). The first of these new rows is number A9 above. Its first four numbers were 1, 16, 27 and 34. These were all taken from the diagonal mentioned above. It meant that this one card would have one number in common with each of the cards A2 to A8… but not the row below A8. There was no way of having anything in common with that row. So I had to delete that row. Which meant I only had symbols 1 to 7 in common with my source card. I’ll leave you to figure out why. Or just skip this bit. Really, it’s not worth it. If you try and follow my logic for rows A10 to A15, you’ll see things got worse and worse.

Really. Skip those two paragraphs above. The paragraphs below are sooooooo much nicer.

Apart from anything else, I abandoned pen and paper and created a spreadsheet.

My attempts in spreadsheet form

All neat and digital and lovely! Huge sighs of relief all round. Now, let’s start again.

There’s another way of thinking about this. Instead of creating just one card for each number in the source card, how about we create seven? Why seven? Well. This is where it all gets super-neat.

Via http://www.carpelibrum.net/2013/12/review-art-of-clean-up-life-made-neat.html

Let’s suppose, just for a minute, that each symbol occurs eight times throughout the deck of cards. At the moment this is just a guess, based on a bit of intuition and the fact that there are eight symbols per card. That would mean there were eight cards containing the number 1 (see diagram a bit lower down).

These eight cards all have one thing in common: the number 1. This means they can’t have anything else in common. Because every card has one thing — and only one thing — in common with every other card in the deck. If we were to pick any two of these eight cards, they would have the number 1 in common. This means that every single one of the other (8 x 7 =) 56 symbols on these eight cards must be a different unique symbol. Ooh! That makes 57 symbols altogether!

OK, I have a confession to make. While I was scribbling my confusing nonsense on my scrap of paper, my other half @AllyFogg was also investigating the problem. His approach was to look at the actual cards in the Dobble deck, one by one, and make notes about what he saw. At this point he was now swearing blind that there were 57 symbols, not 50 as the game instructions claimed. So we did a bit of googling. Sure enough, there are 57 symbols.

OK, this is good. My new approach is making sense. This is what my first eight cards look like now:

So, my next question is, would it be possible to have a ninth card which also contained the number 1? Nuh-uh. Nope. Well… then again… OK. If every single card in the pack contained the number 1, that would work. But every other number on the cards would have to be unique and distinct, making (7 x 55 =) 385 symbols altogether. Which is more than 57, and would make a rubbish game. The point of Dobble is that you try and spot what each pair of cards has in common. In this version, every card would have the same thing in common. So we’ll discount that.

So, what if we had a ninth card with a number 1 on it? Well, as before, every other symbol on that card would have to be new and different, so we end up with more than 57 symbols. But worse than that, what if we try to add a tenth card which doesn’t contain a number 1? This tenth card still has to have something in common with every other card in the deck, including the nine cards we already created. But there are nine of them, and apart from the 1s they have nothing in common with each other. So we would have to choose one symbol from each card … which makes nine symbols. And we only have eight per card. So that’s not possible.

More neatness! Yay!

Via pxleyes.com — created by vonksunday

What we’ve learnt is that each symbol can be repeated no more than eight times in the whole deck. If you’ve peeked at the spreadsheet I made, you might be grasping a pattern, or even a formula if you’re really clever…

Every symbol appears eight times in the deck. Every time you have a subset of eight cards which all contain the same symbol, the other 56 symbols have to be unique and distinct. Above you see eight cards which all contain the number 1. We could do the same thing and create eight cards which all contain the number 2. And again with 3, 4, 5 … all the way up to 8. Each time, our top card would contain the numbers 1 to 8. Each time, the other cards would contain the repeated number… plus all the other numbers, 9 to 57 (= 49 numbers).

So, for instance, this is what the cards containing the number 3 might look like:

If we repeat this pattern for all the numbers 1 to 8, we end up with 57 cards! Yay! Oh. Hang on… Aren’t there 55 cards in a Dobble set, not 57?

More Googling. Thank God for Google. It turns out that although the Dobble set contains 55 cards, it does not represent a perfect mathematical solution. The perfect mathematical solution would contain 57 cards. The same number of cards as there are symbols, in fact. I’ll leave that one as an exercise for the reader, but it does make sense.

The theory is that the Dobble manufacturers used standard card-printing machinery, which is wired for decks of conventional cards, which generally contain 52 cards plus 3 jokers.

Via http://www.quever365.com/como-hacer-una-maleta/

But anyway, the optimum number — the maximum number possible, in fact — is 57.

And it doesn’t take much at this point to see that there is quite a neat formula which we can use to calculate the number of symbols we need, as well as the maximum number of cards possible, depending on how many symbols we have per card.

Let’s say we have n symbols per card. So in our case, n = 8. Each symbol can only appear n times. There will always be one source card, which contains the first n numbers 1 to n.

Source card:

Now, for every symbol on that source card, we will create n minus 1 (7 in our case) new cards. Each batch of n cards will consist of the source card plus n minus 1 other cards. Altogether, those n cards will contain that source-card symbol plus all the other symbols. In our case, there are 56 other symbols. This is 7 x 8, or (n minus 1) x n.

So for every source card symbol, we created a new batch of n minus 1 cards … so altogether we have the source card plus (n minus 1) x n cards… and this gives us our formula, which is

Woohoo! We have a formula! We like formulas, right?

Everything is right with the world.

Via https://twitter.com/dibapaya

Also, we’re getting closer to a full pack which satisfies all the rules. We’re not quite there yet though. We can (hopefully) see that if a pack is possible, then the optimum size will be 57 cards. We can see that the pack can be split into subsets of 7 cards, where every one of the 7 cards has one symbol in common and the other 49 symbols are completely different. But how do we know those 49 symbols can be arranged in such a way that if we take a card from one subset and compare it to a card in another subset, it will always be true that they have one — and only one — symbol in common?

Well, it turns out there is at least one way of doing this. Assuming my spreadsheet doesn’t contain any errors, what I did was take those 49 numbers (the numbers 9 to 57) and repeat them in every subset, but each time I would take each column and shift it round. In the first subset, I just transpose rows into columns, like this: The second subset has all the numbers from the first subset, but rows have turned into columns (for instance, look at the numbers 9 to 15):

Then what I discovered is that for the next subset (where all the cards start with the number 3), I could repeat the pattern used in the one before, but shift everything along slightly.

The first column doesn’t need shifting. The second is shifted along by one number. The third is shifted by two numbers. So in that third column, instead of (23, 24, 25, 26, 27, 28, 29) I get (28, 29, 23, 24, 25, 26, 27).

Hopefully you can see that any card from the second subset shown above will have one — and only one — symbol in common with any card from the first subset. By using the same shifting pattern (no shift in the first column, one shift in the second, and so on) when moving from each subset to the next, I end up with a perfect pack of cards. You can see the whole pack if you view the spreadsheet, but here is another set of subsets so you can see how the pattern progresses:

Each column has to be shifted by a different amount. Otherwise, you end up with something like this, which is what I tried at first:

The problem with this is that if you look closely you’ll see that each subset, once you remove the starting number, actually has identical cards. So, each subset is fine if you compare its cards with the first subset, but if you take a card from one subset and compare it with a card in another subset which is NOT the first subset, it will either have no symbols in common or seven symbols in common (for instance, compare the 9th row with the 15th row: (2, 10, 17, 24, 31, 38, 45, 52) and (3, 10, 17, 24, 31, 38, 45, 52)).

You don’t have to have 57 cards. You can have less than 57 cards. You can take the 57 cards I made and feed one of them to the dog. You can throw three down the loo. You can lose seven of them out of a carelessly-opened car window on a motorway on a windy night. The rest of the pack will still have one — and only one — symbol in common with every other card in the deck.

This makes me happy.

Here are some happy people:

Hopefully you’re happy now, too.

It’s actually all to do with “uniform block design” and “Covering with most possible equal size subsets having pairwise singleton intersections”. So there you go.

Oh, and since I started writing this post, we have now played the game itself. It’s a surprising amount of fun. I recommend it.

Sorry if you don’t like maths. But there’s no way you’re still here if you don’t. And your reward for liking maths enough to read this far is all those happy people in that video above. Do watch it. It made me cry happy tears.

Via http://www.wanista.com/wp-content/uploads/2015/01/happy-faces-360x240.jpg