12
$\begingroup$

In the game Dobble ( known in the USA as "Spot it" ) , there is a pack of 55 playing cards, each with 8 different symbols on them. What is remarkable ( mathematically ) is that any two cards chosen at random from the pack will have one and only one matching symbol . This spurred me on to investigating the Maths behind generating such a pack of cards, starting with much more basic examples with only 2 symbols on each card and gradually working my way up to 8 .

This has been explored extensively in the linked question "What is the Math behind the game Spot it".

What has been established is that if the number of symbols on each card is N, then the maximum number of different symbols throughout the pack is C , the maximum number of cards in a pack is also C, the number of times any given symbol is repeated throughout the pack is N, and N and C are related as follows :

C = N^2 - N + 1 [ N squared minus N plus one ]

But I still do not understand the algorithm for generating the cards from a given symbol set .

I am trying to follow the matrix generated by Don Simborg , but I just can't quite follow his formula . Even for a simple matrix with N=3 and C=7, I know what the matrix should look like , but can't seem to understand his descriptive syntax . For example in column 2, row 4, his formula suggests the symbol is the one numbered 3N-1 in the sequence of 7 symbols, but 3N-1= 8 , so which symbol should I use? Is he making an assumption that we just wrap around (subtract 7) and start counting again from the beginning of the sequence ? But this still generates the wrong symbol . I know from looking at the pattern that it should be either symbol no 4 or symbol no 5, but just can't see how this arises from his formula . If we take the 7 symbols as being the letters "A", "B", "C", "D", "E" and "F", then the matrix should be as follows below :

A B C

A D E

A F G

B D F

B E G

C D G

C E F

Can anyone help me? I've been trying to crack how to generate the symbol arrangements on the "Dobble" cards for months, and have succeeded in generating the sequence as far as N=6, C=31 but I am stuck at N=7 . I would welcome any assistance or enlightenment with this , thank you !

And if I have misunderstood Don Simborg's formula, then the error lies with me !

Here are the matrices I have found from my own trial and error :

For N=4, C=13, with a symbol set being A B C D E F G H I J K L M , the matrix is as follows :

A B C D

A E F G

A H I J

A K L M

B E H K

B F I L

B G J M

C E J L

C F H M

C G I K

D E I M

D F J K

D G H L

For N= 5, C = 21, with the symbol set : A B C D E F G H I J K L M N O P Q R S T U , the matrix is as follows :

A B C D E

A F G H I

A J K L M

A N O P Q

A R S T U

B F K N R

B G J O S

B H L P T

B I M Q U

C F J P U

C G K Q T

C H M N S

C I L O R

D F L Q S

D G M P R

D H K O U

D I J N T

E F M O T

E G L N U

E H J Q R

E I K P S

To state again, both the sets above have the remarkable quality that any two rows chosen at random will have one and only one matching symbol .

$\endgroup$
  • 1
    $\begingroup$ math.stackexchange.com/questions/464932/… $\endgroup$ – user197999 May 29 '15 at 4:09
  • $\begingroup$ Thank you to those who have pointed out that I am duplicating questions asked before, but I am still unable to understand what the algorithm is. I would like to know of a formula for generating the cards from a given sequence of symbols. Thank you . $\endgroup$ – sevanstephan May 29 '15 at 4:32
5
$\begingroup$

Here is an algorithm to generate a projective plane for every N prime. It will work for N power of prime if the computation of "(I*K + J) modulus N" below is made in the correct "field".

// N*N first cards
for I = 0 to N-1
   for J = 0 to N-1
      for K = 0 to N-1
         print ((I*K + J) modulus N)*N + K
      end for
      print N*N + I
      new line
   end for
end for

// N following cards
for I = 0 to N-1
   for J = 0 to N-1
      print J*N + I
   end for
   print N*N + N
   new line
end for

// Last card
for I = 0 to N-1
   print N*N + I
end for
new line
$\endgroup$
  • 3
    $\begingroup$ How does it work? Why does it work? What does it output? $\endgroup$ – Turion Aug 14 '16 at 11:09
1
$\begingroup$

Here is a C code inspired from @karinka's answer with a different arrangement of symbols.

It works for $n$ being a prime number (2, 3, 5, 7, 11, 13, 17, ...).

Number of symbols in a given card = $n + 1$

Total number of cards = $n^2 + n + 1$

Total number of symbols = $n^2 + n + 1$

#include <stdio.h>
#include <stdlib.h>

#define PRINT(x) printf("%2d  ", (x)+1)

main() {
    int i, j, k, r = 0, n = 7;

    // first card
    printf ("Card %2d:  ", ++r);
    for (i = 0; i <= n; i++) {
        PRINT (i);
    }
    printf ("\n");

    // n following cards
    for (j = 0; j < n; j++) {
        printf ("Card %2d:  ", ++r);
        PRINT (0);
        for (k = 0; k < n; k++) {
            PRINT (n+1 + n*j + k);
        }
        printf ("\n");
    }

    // n*n following cards
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf ("Card %2d:  ", ++r);
            PRINT (i+1);
            for (k = 0; k < n; k++) {
                PRINT (n+1 + n*k + (i*k+j)%n); // Good for n = prime number
            }
            printf ("\n");
        }
    }
}

Example output with $n = 3$:

Card  1:   1   2   3   4
Card  2:   1   5   6   7
Card  3:   1   8   9  10
Card  4:   1  11  12  13
Card  5:   2   5   8  11
Card  6:   2   6   9  12
Card  7:   2   7  10  13
Card  8:   3   5   9  13
Card  9:   3   6  10  11
Card 10:   3   7   8  12
Card 11:   4   5  10  12
Card 12:   4   6   8  13
Card 13:   4   7   9  11
$\endgroup$
  • $\begingroup$ Thank you very much, that is very helpful ! $\endgroup$ – sevanstephan Jul 23 '18 at 2:14
1
$\begingroup$

in AutoIt:

$r=1
$n=7

ConsoleWrite("Card" & $r & "=")
for $i= 1 to $n+1
   ConsoleWrite(" " & $i )
Next
ConsoleWrite(@CRLF)
for $j=1 to $n
   $r=$r+1
   ConsoleWrite("Card" & $r & "=")
   ConsoleWrite(" 1")
   for $k=1 to $n
	     ConsoleWrite(" " & $n + $n *($j-1) + $k+1 )
   Next
   ConsoleWrite(@crlf)
Next
for  $i= 1 to $n
   for $j=1 to $n
	  $r=$r+1
	  ConsoleWrite("Card" & $r & "=")
      ConsoleWrite(" " & $i+1 & " ")
	  for $k=1 to $n
		 ConsoleWrite($n + 2 + $n* ($k-1)  + mod(($i-1) *($k-1) +$j-1, $n) & " ")
      Next
      ConsoleWrite(@crlf)
   Next
Next


Result:
Card1= 1 2 3 4 5 6 7 8
Card2= 1 9 10 11 12 13 14 15
Card3= 1 16 17 18 19 20 21 22
Card4= 1 23 24 25 26 27 28 29
Card5= 1 30 31 32 33 34 35 36
Card6= 1 37 38 39 40 41 42 43
Card7= 1 44 45 46 47 48 49 50
Card8= 1 51 52 53 54 55 56 57
Card9= 2 9 16 23 30 37 44 51 
Card10= 2 10 17 24 31 38 45 52 
Card11= 2 11 18 25 32 39 46 53 
Card12= 2 12 19 26 33 40 47 54 
Card13= 2 13 20 27 34 41 48 55 
Card14= 2 14 21 28 35 42 49 56 
Card15= 2 15 22 29 36 43 50 57 
Card16= 3 9 17 25 33 41 49 57 
Card17= 3 10 18 26 34 42 50 51 
Card18= 3 11 19 27 35 43 44 52 
Card19= 3 12 20 28 36 37 45 53 
Card20= 3 13 21 29 30 38 46 54 
Card21= 3 14 22 23 31 39 47 55 
Card22= 3 15 16 24 32 40 48 56 
Card23= 4 9 18 27 36 38 47 56 
Card24= 4 10 19 28 30 39 48 57 
Card25= 4 11 20 29 31 40 49 51 
Card26= 4 12 21 23 32 41 50 52 
Card27= 4 13 22 24 33 42 44 53 
Card28= 4 14 16 25 34 43 45 54 
Card29= 4 15 17 26 35 37 46 55 
Card30= 5 9 19 29 32 42 45 55 
Card31= 5 10 20 23 33 43 46 56 
Card32= 5 11 21 24 34 37 47 57 
Card33= 5 12 22 25 35 38 48 51 
Card34= 5 13 16 26 36 39 49 52 
Card35= 5 14 17 27 30 40 50 53 
Card36= 5 15 18 28 31 41 44 54 
Card37= 6 9 20 24 35 39 50 54 
Card38= 6 10 21 25 36 40 44 55 
Card39= 6 11 22 26 30 41 45 56 
Card40= 6 12 16 27 31 42 46 57 
Card41= 6 13 17 28 32 43 47 51 
Card42= 6 14 18 29 33 37 48 52 
Card43= 6 15 19 23 34 38 49 53 
Card44= 7 9 21 26 31 43 48 53 
Card45= 7 10 22 27 32 37 49 54 
Card46= 7 11 16 28 33 38 50 55 
Card47= 7 12 17 29 34 39 44 56 
Card48= 7 13 18 23 35 40 45 57 
Card49= 7 14 19 24 36 41 46 51 
Card50= 7 15 20 25 30 42 47 52 
Card51= 8 9 22 28 34 40 46 52 
Card52= 8 10 16 29 35 41 47 53 
Card53= 8 11 17 23 36 42 48 54 
Card54= 8 12 18 24 30 43 49 55 
Card55= 8 13 19 25 31 37 50 56 
Card56= 8 14 20 26 32 38 44 57 
Card57= 8 15 21 27 33 39 45 51 
$\endgroup$
  • $\begingroup$ Wonderful, thank you, I understand how you have arrived at the sequences. I am still intrigued to know if there is a way of creating a Dobble set with 7 symbols per card? From what I understand from the above posts, as (7-1) is not a prime number, then it makes it impossible to generate a set using the algorithms above . But is there another way of doing so? I have found the Dobble set for 5 symbols, but it could not be done by simply cycling the matrix forward by 1; instead if certain indices cycled backwards whilst others cycled forward, then a correct set was generated. $\endgroup$ – sevanstephan Jul 23 '18 at 2:37
1
$\begingroup$

The generators submitted by Karinka, Urmil Karikh and Uwe are working nicely. However, original answer aimed at understanding the algorithm. The theory behind all three generators are in (See Paige L.J., Wexler Ch., A Canonical Form for Incidence Matrices of Projective Planes...., In Portugalie Mathematica, vol 12, fasc 3, 1953). It is generating Incidence matrix for projective plane of $q$th order in the normal form ($q=N-1$). Every row of incidence matrix corresponds to one card and column indexes where there are ones in the matrix, correspond to symbol on the card. Permutation Matrices, marked in the article as $C_{ij}$ are generated by cycling the identity matrix column-wise by $(i-1)(j-1) \mod q$ rows. This works only if $q$ is prime number, hence no divisors of zero exist in Galois field $GF(q)$. For $q$ not being prime, but only prime power, these permutation matrices $C_{ij}$ would have to be generated another way (i.e. neither addition nor multiplication groups of $GF(q)$ are not ordinary multiplication or addition, it has to be constructed using irreducible polynomials). So, above algorithms would not work for $q$ equal to $4$, $8$ or $9$. Anyway, from this matrix, you can nicely see that the two line (cards) has exactly one point (symbol) in common and vice-versa. Also, you can see that one symbol is on exactly $N$ cards and one card has exactly $N$ symbols (assuming that all 57 cards of Dobble would be printed and not only 55).

$\endgroup$
  • $\begingroup$ Thank you for your explanation . I think I understand what you have written, although I am hindered by my restricted knowledge of academic mathematical language . Am I correct is saying that it is not possible to generate a set of cards which have 7 symbols using the algorithms posted? I have managed to find a set for 5 symbols, please see below . $\endgroup$ – sevanstephan Jul 23 '18 at 3:26
1
$\begingroup$

This is How I've converted the algorithm in javascript:

"use strict"

var i, j, k var r=1 var n=7

var res = ''; res = "Card" + r + "=" for (i = 1; i<= n+1; i++) { res += " " + i } console.log(res) for (j=1; j<=n; j++) { r=r+1 res = "Card" + r + "="; res += " 1"; for (k=1; k<=n; k++) { res += " " + (n + n * (j-1) + k+1) } console.log(res) } for (i= 1; i<=n; i++) { for (j=1; j<=n; j++) { r=r+1 res = "Card" + r + "=" res += " " + (i+1) + " " for (k=1; k<= n; k++) { res += n + 2 + n * (k-1) + (((i-1) * (k-1) +j-1) % n) + " " } console.log(res) } }

$\endgroup$
0
$\begingroup$

Good thing I was able to write a program to check. the first listed failure are the lines

2     8    14    20    26    32    38
4     8    16    24    26    34    42

which overlap in the two numbers $8,26.$ Note that a projective plane of "order" $6$ is impossible. I was not $100\%$ sure that this list would amount to a projective plane, but I guess it does, therefore was doomed to failure.

I seem to have 7 symbols per card. I will need to write a computer program to compare the different cards. I found an algorithm, as I was doing this it seemed right, but maybe... Below see the $43$ cards, symbols are the numbers from $1$ to $43.$

$$ 1,2,3,4,5,6,7, $$ $$ 1,8,9,10,11,12,13,$$ $$ 1,14,15,16,17,18,19,$$ $$ 1,20,21,22,23,24,25, $$ $$ 1,26,27,28,29,30,31, $$ $$ 1,32,33,34,35,36,37, $$ $$ 1,38, 39,40,41,42,43,$$

$$ 2,8,14,20,26,32,38,$$ $$ 2,9,15,21,27,33,39,$$ $$ 2,10,16,22,28,34,40,$$ $$ 2,11,17,23,29,35,41,$$ $$ 2,12,18,24,30,36,42,$$ $$ 2,13,19,25,31,37,43,$$

$$ 3,8,15,22,29,36,43,$$ $$ 3,9,16,23,30,37,38,$$ $$ 3,10,17,24,31,32,39,$$ $$ 3,11,18,25,26,33,40,$$ $$ 3,12,19,20,27,34,41,$$ $$ 3,13,14,21,28,35,42,$$

$$ 4,8,16,24,26,34,42,$$ $$ 4,9,17,25,27,35,43,$$ $$ 4,10,18,20,28,36,38,$$ $$ 4,11,19,21,29,37,39,$$ $$ 4,12,14,22,30,32,40,$$ $$ 4,13,15,23,31,33,41,$$

$$ 5,8,17,20,29,32,41,$$ $$ 5,9,18,21,30,33,42,$$ $$ 5,10,19,22,31,34,43,$$ $$ 5,11,14,23,26,35,38,$$ $$ 5,12,15,24,27,36,39,$$ $$ 5,13,16,25,28,37,40,$$

$$ 6,8,18,22,26,36,40,$$ $$ 6,9,19,23,27,37,41,$$ $$ 6,10,14,24,28,32,42,$$ $$ 6,11,15,25,29,33,43,$$ $$ 6,12,16,20,30,34,38,$$ $$ 6,13,17,21,31,35,39,$$

$$ 7,8,19,24,29,34,39,$$ $$ 7,9,14,25,30,35,40,$$ $$ 7,10,15,20,31,36,41,$$ $$ 7,11,16,21,26,37,42,$$ $$ 7,12,17,22,27,32,43,$$ $$ 7,13,18,23,28,33,38,$$

$\endgroup$
  • $\begingroup$ Hi Will Jagy, thanks for your reply . However, in Dobble you must have one and only one matching number in any pair of cards . $\endgroup$ – sevanstephan Jul 23 '18 at 0:43
  • $\begingroup$ Hi Will Jagy, thanks for your reply . However, in Dobble you must have one and only one matching number in any pair of cards . For Example you have listed 2,8,14,20,26,32,38 as one card and later 5,8,17,20,29,32,41 as another card and there are three matching numbers ( namely 8,20 and 32). I have been working on the Dobble problem for a few years. At first I too thought it was a case of cycling patterns of symbols, but the process of cycling generates multiple matches, rather than just one, which is required in Dobble. I have been looking at random sequences but it is a very subtle Problem. $\endgroup$ – sevanstephan Jul 23 '18 at 1:50
0
$\begingroup$

These help implementing @karinka's algorithm for p = 2^2 and p = 2^3 so you can easily get 4, 5, 6, 8 and 9 symbols per card for example. 10 symbols per card is also easy (p = 3^2) but there is no finite field of order 6 or 10, so 7 and 11 symbols per card cannot be generated (unless you allow more symbols than cards).

var GF4add = [
 [0, 1, 2, 3],
 [1, 0, 3, 2],
 [2, 3, 0, 1],
 [3, 2, 1, 0]
];

var GF4mul = [
 [0, 0, 0, 0],
 [0, 1, 2, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2]
];

var GF8add = [
 [0, 1, 2, 3, 4, 5, 6, 7],
 [1, 0, 3, 2, 5, 4, 7, 6],
 [2, 3, 0, 1, 6, 7, 4, 5],
 [3, 2, 1, 0, 7, 6, 5, 4],
 [4, 5, 6, 7, 0, 1, 2, 3],
 [5, 4, 7, 6, 1, 0, 3, 2],
 [6, 7, 4, 5, 2, 3, 0, 1],
 [7, 6, 5, 4, 3, 2, 1, 0]
];

var GF8mul = [
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 2, 3, 4, 5, 6, 7],
 [0, 2, 4, 6, 5, 7, 1, 3],
 [0, 3, 6, 5, 1, 2, 7, 4],
 [0, 4, 5, 1, 7, 3, 2, 6],
 [0, 5, 7, 2, 3, 6, 4, 1],
 [0, 6, 1, 7, 2, 4, 3, 5],
 [0, 7, 3, 4, 6, 1, 5, 2]
];

function mul(a, b, n)
{
    if (n == 4)
        return GF4mul[a][b];
    else if (n == 8)
        return GF8mul[a][b];
    else
        return (a * b) % n;
}

function add(a, b, n)
{
    if (n == 4)
        return GF4add[a][b];
    else if (n == 8)
        return GF8add[a][b];
    else
        return (a + b) % n;
}
$\endgroup$
0
$\begingroup$

Dobble set for 5 symbols . Note that in cards 10 to 21, some of the indices cycle down whilst others cycle up. It was not possible to create a set if all the indices cycled in the same direction . I am still working on the Dobble set for 7 symbols .

Card 1 : 1, 2, 3, 4, 5

Card 2 : 1, 6, 7, 8, 9

Card 3 : 1, 10, 11, 12, 13

Card 4 : 1, 14, 15, 16, 17

Card 5 : 1, 18, 19, 20, 21

Card 6 : 2, 6, 10, 14, 18

Card 7 : 2, 7, 11, 15, 19

Card 8 : 2, 8, 12, 16, 20

Card 9 : 2, 9, 13, 17, 21

Card 10 : 3, 6, 11, 16, 21

Card 11 : 3, 7, 10, 17, 20

Card 12 : 3, 8, 13, 14, 19

Card 13 : 3, 9, 12, 15, 18

Card 14 : 4, 6, 12, 17, 19

Card 15 : 4, 7, 13, 16, 18

Card 16 : 4, 8, 10, 15, 21

Card 17 : 4, 9, 11, 14, 20

Card 18 : 5, 6, 13, 15, 20

Card 19 : 5, 7, 12, 14, 21

Card 20 : 5, 8, 11, 17, 18

Card 21 : 5, 9, 10, 16, 19

$\endgroup$
0
$\begingroup$

Here is VBA code inspired from @karinka's and @Urmil Parikh answers but using an arrangement of symbols to match answers from @Urmil Parikh, @Uwe, and @Will Jagy.
You can swap the commented lines to print letters, though they won't match the pattern from the original question.

I realize there isn't anything new in my answer but I wanted to convert it to VBA so I could try out the code in an environment I have on hand, Excel. I'm hoping this can help someone else.

I don't quite grasp the comments about n being a prime number. This algorithm works when n is 4 or 8 (meaning 5 or 9 symbols per card).

Public Sub Generate()
' This will generate unique cards similar to "Spot it!" or "Dobble".

    Dim i, j, k, n, s, r

    ' How many symbols are on each card?
    ' Valid numbers are 3, 4, 5, 6, 8, 9, 10.  7 and 11 will not generate correctly.
    ' If s is 7, cards 8, 20, and 26 will match more than one card for numbers 8, 20, 32
    s = 4

    Debug.Print (s * s) - s + 1 & " unique cards will be generated with " & s & " symbols per card."

    n = s - 1 ' Reduce by 1 since all calcs are base 0.

    '--- First card
    r = 1
    Debug.Print "Card " & r & ": ",
    For i = 0 To n
        Debug.Print i + 1;
        'Debug.Print Chr(i + 65), ' Alternative to print letters
    Next
    Debug.Print

    '--- N following cards
    For i = 0 To n - 1
        r = r + 1
        Debug.Print "Card " & r & ": ",
        Debug.Print 1;
        'Debug.Print "A",
        For j = 0 To n - 1
            Debug.Print n + 1 + (n * i) + j + 1;
            'Debug.Print Chr(n + 1 + (n * i) + j + 65), ' Alternative to print letters
        Next
        Debug.Print
    Next

    '--- N*N following cards
    For i = 0 To n - 1
        For j = 0 To n - 1
            r = r + 1
            Debug.Print "Card " & r & ": ",
            Debug.Print i + 2;
            'Debug.Print Chr(i + 66),
            For k = 0 To n - 1
                Debug.Print (n + 1) + (n * k) + ((i * k + j) Mod n) + 1;
                'Debug.Print Chr((n + 1) + (n * k) + ((i * k + j) Mod n) + 65), ' Alternative to print letters
            Next
            Debug.Print
        Next
    Next

End Sub

Sample output

13 unique cards will be generated with 4 symbols per card.
Card 1:        1  2  3  4 
Card 2:        1  5  6  7 
Card 3:        1  8  9  10 
Card 4:        1  11  12  13 
Card 5:        2  5  8  11 
Card 6:        2  6  9  12 
Card 7:        2  7  10  13 
Card 8:        3  5  9  13 
Card 9:        3  6  10  11 
Card 10:       3  7  8  12 
Card 11:       4  5  10  12 
Card 12:       4  6  8  13 
Card 13:       4  7  9  11 

7 unique cards will be generated with 3 symbols per card.
Card 1:       A             B             C             
Card 2:       A             D             E             
Card 3:       A             F             G             
Card 4:       B             D             F             
Card 5:       B             E             G             
Card 6:       C             D             G             
Card 7:       C             E             F          

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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