1

I've played Dobble and asked myself it is possible to have instead of pairs, $n$ cards having one symbol in common, for example for $n=3$ if you take any three cards they only have one symbol in common. I've found two trivial solutions ; the first with only a single symbol shared by all cards, and the second one is every unique combination of $n$ cards has its own unique symbol.

Dobble is a game with 55 Cards, any two cards of the 55 Cards only share one symbol.

Soheil
  • 11
  • There are $\binom n3$ subsets of size $3$, so for each of those create a special symbol and distribute to those people (and only those people). this generalizes to subsets of size $k$ in the obvious way. – lulu Jun 12 '23 at 16:52
  • Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. – Community Jun 12 '23 at 16:56
  • 1
    Shouldn't you describe Dobble. People may not know about it ? At least I don't ! – true blue anil Jun 12 '23 at 17:23
  • 1
    @true blue anil https://en.wikipedia.org/wiki/Dobble This is a fascinating game to play with kids in particular. Fascinating also by the fact that it is based on finite projective planes. – Jean Marie Jun 12 '23 at 17:59
  • 2
    Obligatory youtube link to Matt Parker's (stand-up maths) video about the maths of dobble. The most surprising thing to me was that the standard dobble printing left out two additional possible cards for some unknown reason. – JMoravitz Jun 12 '23 at 18:10

2 Answers2

2

Let us consider the case of $6$ cards meeting the constraint "any group of 3 cards has a single common symbol" ; an elementary solution exists which can be described by the following boolean array where the $6$ cards are represented by the lines and the $20 = \binom{6}{3}$ symbols are represented by the columns :

$$\begin{matrix} 1&1&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0&0\\ 1&1&1&1&0&0&0&0&0&0&1&1&1&1&1&1&0&0&0&0\\ 1&0&0&0&1&1&1&0&0&0&1&1&1&0&0&0&1&1&1&0\\ 0&1&0&0&1&0&0&1&1&0&1&0&0&1&1&0&1&1&0&1\\ 0&0&1&0&0&1&0&1&0&1&0&1&0&1&0&1&1&0&1&1\\ 0&0&0&1&0&0&1&0&1&1&0&0&1&0&1&1&0&1&1&1\end{matrix}$$ The problem is that this "brute-force" solution it necessitates already 20 symbols for only 6 cards ; with 10 cards, one would have to use $\binom{10}{3}=120$, etc. !

But there is a way to "narrow" the number of symbols. See the second array in the sequel.

How have I obtained such an array ? More or less in the same vein as for Dobble, by using finite fields. More precisely by considering planes (instead of lines for Dobble) in an adequate finite 3D space with affine equations

$$ax+by+cy=d,$$

(completely defined by their "normal" vector $(a,b,c)$ and value $d$)

Indeed, as it is the case for 3D affine space $\mathbb{R^3}$, the intersection of 3 affine planes whose normal vectors are independent is reduced to a point.

Here is such an explicit set of cards using (in the background) finite field $\mathbb{F_5}$ (recall : Dobble is based on finite field $\mathbb{F_7}$) :

 Plane 1: 1   0   1   0   1   1   0   1   0   0   1  
 Plane 2: 1   1   0   1   0   0   1   1   0   1   0
 Plane 3: 1   0   0   0   1   0   1   0   1   1   1
 Plane 4: 1   1   1   1   0   1   0   0   1   0   0
 Plane 5: 0   1   0   0   1   1   0   1   1   1   0
 Plane 6: 0   0   1   1   0   0   1   1   1   0   1

where each of the eleven columns represents a point in the finite three-dimensional vector space $(\mathbb{F_5})^3$, which has $5^3=125$ points.

(boolean value $1$ represents the fact that a certain point belongs to a certain plane).

Said otherwise, if we take as symbols the first 11 letters of the roman alphabet, the "cards" will be :

$$\begin{array}{l} ACEFHK\\ABDGHJ\\AEGIJK\\ABCDFI\\BEFHIJ\\CDGHIK\end{array}$$

Remark : one can observe that, in the previous array, 8 columns have three "$1$"s (like in the first array) but three of them have four "$1$"s : with each of these three columns, one can generate 4 groups of $3$. If we totalize, one gets $8+3 \times 4=20$ : we find back the number of columns of the first array.

I could give details, but I am awaiting you, Sohei, to react to my proposal. I insist on the fact that one of the main issue in the ratio "number of cards vs. number of symbols" for the game to be "playable"...

Thanks to @Mike Earnest who has recalled me the independence criteria for the normal vectors in order that there is a (unique) solution. It is his remark that make me realize that we can work in an ordinary (non projective) finite vector space.

Jean Marie
  • 81,803
  • See the didactic accpted answer to this question here for the projective space associated with vector space $(\mathbb{F_3})^2$ with its $3^2+3+1$ planes... – Jean Marie Jun 12 '23 at 18:58
  • See as well this reference – Jean Marie Jun 12 '23 at 22:21
  • 1
    @Mike Earnest Thanks for your objection ; a remedy is to consider a (maximal) subset of planes having 3 by 3 their associated $v_1,v_2,v_3$ independent. I must do explicit calculations for example in the space considered in the references I have given. – Jean Marie Jun 13 '23 at 06:05
  • An important keyword for placing your question in a wider context: "(Combinatorial) Design Theory – Jean Marie Jun 13 '23 at 13:25
  • Thanks for the answer, 6 symbols each for a 6 card game sounds really promising, does this scale well? If it stays about the same number of symbols on each card as there are cards, that would sound playable. – Soheil Jun 15 '23 at 03:13
  • An objective that sounds hard to achieve... On your side, which methodology have you used ? Do you have interesting results/observations to share ? – Jean Marie Jun 15 '23 at 05:02
1

Here is a general method to construct a Dobble variant deck where any $n$ cards have a unique symbol in common. This generalizes the method used in Jean Marie's answer.

  1. Let $F$ be a finite field. Say that $|F|=q$, so $q$ is a prime power.
    Let $V=F^{n+1}$.

  2. Find a list, $C$, of vectors in $V$, such that any $n$ distinct vectors in $C$ are linearly independent. I call this property "$n$-wise linearly independent." $C$ will be the set of cards.

    • Finding a list of $m$ vectors in $F^{n+1}$ which are $n$-wise independent is equivalent to finding a $[m,m-n-1,n+1]_q$ code. Specifically, given such a code, its parity check matrix is a $(n+1)\times m$ matrix with elements in $F$, and the columns of this matrix will be $n$-wise independent. I learned this from this MO question and answer.
      There is no general method to determine the largest $m$ such that a $[m,m-n-1,n+1]_q$ exists, as far as I know. In practice, you need to consult a database of known codes, such as http://www.codetables.de.

  3. Let $S$ be the set of vectors in $V$ whose leftmost nonzero coordinate is equal to $1$. There are $q^n + q^{n-1} + \dots + q + 1$ vectors in $S$. $S$ will be the set of symbols.

  4. For each $c\in C$, and each $s\in S$, symbol $s$ appears on card $c\cdot s=0$, where $\cdot$ is the dot product performed with finite field arithmetic.

Given any $n$ cards, with vectors $c_1,\dots,c_n$, we know by assumption that the list of vectors in linearly independent. Therefore, the system of $n$ equations, defined by $c_i\cdot v=0$ for each $i\in \{1,\dots,n\}$, has a one-dimensional subspace of solutions. There is a unique representative in this subspace whose first nonzero coordinate is $1$, corresponding to the unique symbol shared by all cards.

Example 1

Let $F=\mathbb Z/2\mathbb Z$, and let $n=3$. The columns of this $4\times 8$ matrix are three-wise linearly independent. The eight columns are the eight vectors in $(\mathbb Z/2\mathbb Z)^4$ with an odd number of ones. $$ \begin{bmatrix} 1&0&0&0&0&1&1&1\\ 0&1&0&0&1&0&0&0\\ 0&0&1&0&1&1&0&1\\ 0&0&0&1&1&1&1&0 \end{bmatrix} $$

Following the method described above, here is the resulting Dobble card set produced. Each binary vector is interpreted as a binary integer between $1$ and $14$ for the representation below. There are $8$ cards, with $7$ symbols per card, using $14$ symbols total. Since $n=3$, any $3$ cards have a unique symbol in common.

Card    1:    2    4    6    8   10   12   14 
Card    2:    1    4    5    8    9   12   13 
Card    4:    1    2    3    8    9   10   11 
Card    7:    3    5    6    8   11   13   14 
Card    8:    1    2    3    4    5    6    7 
Card   11:    3    4    7    9   10   13   14 
Card   13:    2    5    7    9   11   12   14 
Card   14:    1    6    7   10   11   12   13

Example 2

Now, let us construct a set of cards where any $4$ have a unique intersection. We will $F = \mathbb Z/3\mathbb Z$ as our field, so we need a collection of vectors in $F^5$ which are $4$-wise linearly independent. It turns out that the columns of the parity check matrix for the $[11,6,5]_3$ ternary Golay code serve this purpose. Initially, this produces an $11$ card deck with $40$ symbols per card, spanning a total of $3^4+3^3+3^2+3^1+1=121$ symbols. However, of these symbols, $55$ symbols appear on $3$ or fewer cards. These symbols can be safely deleted from the cards they appear on while preserving the $4$-intersecting property.

Here is the final deck design. There are $11$ cards, with $30$ symbols per card, spanning $66$ symbols total. This would make for a very challenging game!

Card #  1
   2,   4,   6,  10,  12,  17,  18,  25,  28,  30,  35,  36,  47,  54,  59
  69,  73,  75,  83,  85,  87,  91,  93,  99, 104, 106, 110, 112, 114, 119

Card #  2
   3,   4,   5,   9,  10,  11,  24,  25,  33,  35,  40,  45,  47,  54,  55
  56,  69,  75,  84,  85,  86,  90,  91,  92, 105, 106, 114, 115, 116, 120


Card #  3
   1,   4,   7,  11,  17,  18,  21,  24,  27,  30,  33,  40,  47,  56,  59
  63,  69,  73,  83,  86,  89,  90,  93,  96, 100, 106, 109, 112, 115, 117


Card #  4
   2,   3,   7,  11,  12,  20,  21,  25,  27,  35,  36,  40,  45,  55,  59
  60,  69,  73,  82,  86,  87,  91,  96, 100, 104, 105, 108, 112, 116, 118


Card #  5
   1,   5,   6,   9,  17,  20,  21,  25,  28,  33,  36,  40,  47,  55,  59
  60,  63,  75,  81,  85,  89,  92,  93, 100, 104, 105, 110, 111, 115, 118


Card #  6
   0,   5,   7,  10,  12,  17,  20,  24,  28,  30,  35,  40,  45,  56,  60
  63,  73,  75,  82,  84,  89,  92,  96,  99, 104, 106, 109, 111, 116, 119


Card #  7
  81,  82,  83,  84,  85,  86,  87,  89,  90,  91,  92,  93,  96,  99, 100
 104, 105, 106, 108, 109, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120


Card #  8
   0,   1,   2,   3,   4,   5,   6,   7,   9,  10,  11,  12,  17,  18,  20
  21,  24,  25, 108, 109, 110, 111, 112, 114, 115, 116, 117, 118, 119, 120


Card #  9
   0,   1,   2,   3,   4,   5,   6,   7,  27,  28,  30,  33,  35,  54,  55
  56,  59,  60,  81,  82,  83,  84,  85,  86,  87,  89, 117, 118, 119, 120


Card # 10
   0,   1,   2,   9,  10,  11,  18,  20,  27,  28,  36,  45,  47,  54,  55
  56,  63,  73,  81,  82,  83,  90,  91,  92,  99, 100, 108, 109, 110, 120


Card # 11
   0,   3,   6,   9,  12,  18,  21,  24,  27,  30,  33,  36,  45,  54,  60
  63,  69,  75,  81,  84,  87,  90,  93,  96,  99, 105, 108, 111, 114, 117

Example 3

This example is again for $n=3$ cards at a time. There are $26$ cards, with $30$ symbols per card, spanning $130$ symbols, where any three cards have a unique symbol in common. Each symbol is an integer between $0$ and $155$, but there are $26$ numbers in that range which do not appear on any cards. Every symbol which is used appears $6$ cards.

The field I used is $\mathbb Z/5\mathbb Z$. The $3$-wise linearly independent set of vectors comes from the columns of the parity-check matrix for the $[26,22,4]_5$ code described at http://www.codetables.de/BKLC/BKLC.php?q=5&n=26&k=22.

Card # 1 :
   3,   6,  14,  17,  20,  25,  33,  36,  44,  47,  52,  55,  63,  66,  79
  82,  85,  93,  96, 101, 109, 112, 115, 123, 127, 130, 138, 141, 149, 153

Card # 2 :
   5,   6,   7,   8,   9,  35,  36,  37,  38,  65,  66,  67,  68,  69,  95
  96,  97,  98,  99, 100, 101, 102, 103, 104, 130, 131, 132, 133, 134, 155


Card # 3 :
   0,   6,  12,  18,  24,  26,  32,  38,  44,  45,  52,  58,  65,  71,  78
  84,  85,  91,  97, 104, 105, 111, 117, 123, 126, 132, 138, 144, 145, 151


Card # 4 :
   2,   7,  12,  17,  22,  25,  30,  35,  40,  45,  53,  58,  63,  68,  73
  76,  86,  91,  96, 104, 109, 114, 119, 124, 128, 133, 138, 143, 148, 150


Card # 5 :
   3,   7,  11,  15,  24,  29,  33,  37,  45,  50,  59,  63,  67,  71,  76
  80,  89,  93,  97, 102, 106, 110, 119, 123, 126, 130, 139, 143, 147, 154


Card # 6 :
   1,   6,  11,  16,  21,  27,  32,  37,  42,  47,  53,  58,  63,  68,  73
  79,  84,  89,  99, 100, 105, 110, 115, 120, 126, 131, 136, 141, 146, 150


Card # 7 :
   3,   8,  13,  18,  23,  27,  32,  37,  42,  47,  51,  61,  66,  71,  75
  80,  85,  90,  95, 104, 109, 114, 119, 124, 129, 134, 139, 144, 149, 150


Card # 8 :
   3,   9,  10,  16,  22,  26,  32,  38,  44,  45,  54,  55,  61,  67,  73
  77,  89,  90,  96, 100, 106, 112, 118, 124, 128, 134, 135, 141, 147, 151


Card # 9 :
   2,   8,  14,  15,  21,  29,  30,  36,  42,  48,  51,  63,  69,  70,  78
  84,  85,  91,  97, 100, 106, 112, 118, 124, 127, 133, 139, 140, 146, 151


Card # 10 :
   2,   5,  13,  16,  24,  26,  34,  37,  40,  48,  50,  58,  61,  69,  79
  82,  85,  93,  96, 103, 106, 114, 117, 120, 129, 132, 135, 143, 146, 153


Card # 11 :
  10,  11,  12,  13,  14,  30,  31,  32,  33,  34,  50,  51,  52,  53,  54
  95,  96,  97,  98,  99, 115, 117, 118, 119, 145, 146, 147, 148, 149, 155


Card # 12 :
   0,   9,  13,  17,  21,  27,  31,  35,  44,  48,  54,  58,  62,  66,  70
  76,  80,  89,  93,  97, 103, 111, 115, 124, 127, 131, 135, 144, 148, 154


Card # 13 :
   1,   5,  14,  18,  22,  25,  34,  38,  42,  54,  58,  62,  66,  70,  78
  82,  86,  90,  99, 102, 106, 110, 119, 123, 129, 133, 137, 141, 145, 154


Card # 14 :
   1,   8,  10,  17,  24,  29,  31,  38,  40,  47,  52,  59,  61,  68,  70
  75,  82,  89,  91,  98, 103, 105, 112, 119, 128, 130, 137, 144, 146, 152


Card # 15 :
   4,   6,  13,  15,  22,  26,  33,  35,  42,  53,  55,  62,  69,  71,  75
  82,  89,  91,  98, 102, 109, 111, 118, 120, 127, 134, 136, 143, 145, 152


Card # 16 :
   4,   5,  11,  17,  23,  29,  30,  36,  42,  48,  54,  55,  61,  67,  73
  79,  80,  86,  98, 104, 105, 111, 117, 123, 125, 131, 137, 143, 149, 151


Card # 17 :
   2,   9,  11,  18,  20,  27,  34,  36,  45,  52,  59,  61,  68,  70,  77
  84,  86,  93,  95, 102, 109, 111, 118, 120, 125, 132, 139, 141, 148, 152


Card # 18 :
   4,   8,  12,  16,  20,  27,  31,  35,  44,  48,  50,  59,  63,  67,  71
  78,  82,  86,  90,  99, 101, 105, 114, 118, 128, 132, 136, 140, 149, 154


Card # 19 :
   1,   9,  12,  15,  23,  26,  34,  37,  40,  48,  51,  59,  62,  65,  73
  76,  84,  90,  98, 101, 109, 112, 115, 123, 125, 133, 136, 144, 147, 153


Card # 20 :
  20,  21,  22,  23,  24,  30,  31,  32,  33,  34,  65,  66,  67,  68,  69
  75,  76,  77,  78,  79, 110, 111, 112, 114, 135, 136, 137, 138, 139, 155


Card # 21 :
   0,   7,  14,  16,  23,  29,  31,  38,  40,  47,  53,  55,  62,  69,  71
  77,  84,  86,  93,  95, 101, 110, 117, 124, 129, 131, 138, 140, 147, 152


Card # 22 :
   4,   7,  10,  18,  21,  25,  33,  36,  44,  47,  51,  59,  62,  65,  73
  77,  80,  91,  99, 103, 106, 114, 117, 120, 126, 134, 137, 140, 148, 153


Card # 23 :
 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139
 140, 141, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155


Card # 24 :
   0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14
  15,  16,  17,  18,  20,  21,  22,  23,  24, 150, 151, 152, 153, 154, 155


Card # 25 :
   0,   1,   2,   3,   4,  25,  26,  27,  29,  50,  51,  52,  53,  54,  75
  76,  77,  78,  79, 100, 101, 102, 103, 104, 125, 126, 127, 128, 129, 155


Card # 26 :
   0,   5,  10,  15,  20,  25,  30,  35,  40,  45,  50,  55,  65,  70,  75
  80,  85,  90,  95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150
Mike Earnest
  • 75,930