Dobble Algorithm for three or more matches.

139 Views Asked by At

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.

2

There are 2 best solutions below

6
On

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.

1
On

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