Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the Dobble card game there is a deck of 55 cards. Each of them has 8 symbols on it. There is a total of 50 different symbols and each two cards have one and only one in common.

I am wondering, given a total number of symbols N and a number of symbols on each card K, how do you find the biggest number of cards such that:

  • on each of those cards there are exactly K of the N symbols,
  • every two cards have one and only one symbol in common.
share|improve this question

marked as duplicate by hardmath, Cameron Buie, William, Jared, Andrey Rekalo Aug 13 '13 at 6:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
Here is a very nice page on the mathematical aspects of Dobble. images.math.cnrs.fr/Dobble-et-la-geometrie-finie.html Unfortunately it's in french but google translate should help you... –  Denis Aug 11 '13 at 12:16
    
The linked page connects the Dobble card game with a projective design of order $7$, thus having $7+1 = 8$ symbols per card. This projective design would actually provide $57 = 7^2 + 7 + 1$, but as the article notes the game manufacturer decided to omit two cards. –  hardmath Aug 13 '13 at 5:29
    
Another Dobble game motivated Question. –  hardmath Aug 13 '13 at 6:01

1 Answer 1

up vote 2 down vote accepted

A combinatorial term that applies is uniform block design. Here the word uniform means all blocks contain the same number of points (8 symbols, in the case described).

One supposes (although not explicitly stated) that of the 50 different symbols (see endnote), each appears on some card. But with 8 symbols on each of 55 cards, it is not possible that all symbols appear an equal number of times. Nor is it possible that every symbol is shared by an equal number of pairs of Dobble cards (though perhaps every symbol is shared by at least one pair).

A similar question was posted here recently, also about the maximum number of blocks subject to uniform size and singleton intersections of (distinct) block pairs. Since posting my Answer there, I've progressed a bit in understanding these designs and found some relevant literature that, as yet, I've not added to that post.

Given the partial nature of that Answer, I'm going to summarize it and preview my further investigations, but mark this as Community Wiki and vote to close the Question itself as a duplicate. This is not a criticism of the Question, which I think is excellent, but an expression of the Community policy to keep duplication to a minimum.

The property that every pair of cards shares exactly one common symbol is more often treated from the dual viewpoint, taking the cards to be "points" of an incidence design whose "lines" are defined by the symbols (i.e. the collection of cards that contain a given symbol). In this "dual design" the lines (blocks) are not equal in size (necessarily), but the number of "points" on a (dual) line is always the same. This property is called regularity.

More important is that the singleton intersections of our original blocks (the sets of symbols common to one card) becomes a property that every pair of dual points is incident to exactly one dual line. This dual design is thus what is termed a (nontrivial) pairwise balanced design (PBD).

An important result, a generalization of Fisher's inequality, then applies to this dual design and allows us to conclude that the number of dual lines (symbols) is greater than or equal to the number of dual points (card in the original design). It also tells us that equality (maximizing the number of cards to equal the number of symbols) can only happen with projective designs.

Sadly there are projective designs known for only certain parameters, constructed from finite fields and thus associated with their prime power orders. It is an open conjecture that these are the only projective design orders (although the same prime power may give rise to nonisomorphic projective designs in some cases, but involving the same number of points/lines). The dual of a projective design is again a projective design (though not necessarily the same design).

In looking for more flexible design parameters I came across work by Osvaldo Marrero, starting with his 1970 dissertation, Modular Hadamard Matrices And Related Combinatorial Designs. Specifically related to the present Question are what Marrero calls pseudo-$(v,k,1)$ designs, which amounts to the case of having one fewer block (card) than points (symbols) in terms of the "original" design, which are completely characterized. Here $v$ is the number of points (symbols) and $k$ is the number of those per block (card).

Note: The count of 50 symbols is incorrect, since the theory tells us there must be at least as many symbols as cards in these designs. Actually the documentation (Dobble is also sold under the Spot It! brand) says, "There are more than 50 symbols in all." The French Wikipedia article links indirectly to a Scribd article which claims at the end to have verified "by hand" a count of 57 symbols. Removing two blocks (cards) out of 57 from a projective design of order 7 would indeed leave all 57 points (symbols) appearing in more than one remaining block.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.