Ponder This Challenge - May 2024 - Possible Dobble decks

This problem was suggested by Lorenzo Gianferrari Pini and Radu-Alexandru Todor - thanks!

Dobble® is a card game in which each card contains eight symbols, and any two Dobble cards in the deck share exactly one symbol. A standard Dobble deck consists of 55 cards and 57 symbols. However, it is possible to have a deck of 57 cards and 57 symbols.

In general, given a number $N$, which is a prime power, it is possible to find a Dobble-like deck where each card contains $N+1$ symbols, and there are $N^2+N+1$ cards and symbols in the deck. Dobble itself corresponds to the case $N=7$.

Your goal: For $N=4$, find the number of all possible Dobble-like decks with $N^2+N+1$ cards and symbols, and $N+1$ symbols per card, where each pair of cards has exactly one common symbol.

A Bonus "*" will be given for finding the number of all possible Dobble-like decks for $N=8$.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  May 2024 Solution:

  The numerical solutions are: * Main problem: 422378820864000 * Bonus: 90399509839271079668491458784005740889517921781547218950513473999637402251071324160000000000000000

  There are several approaches to find those numbers; we present only one.

  A Dobble-like deck corresponding to a parameter $N$ is equivalent to a **projective plane** of order N. This is a set of $N^2+N+1$ points and $N^2+N+1$ lines such that every line contains exactly $N+1$ points, and every two lines intersect at exactly one point (think of a projective plane as a generalization of the Euclidean plane, with the difference that there are no parallel lines).

  There is only one projective plane of order 4 and only one of order 8, up to isomorphism. Since we consider isomorphic decks as distinct if there are cards which differ in their symbols, given a Dobble deck we also need to count all the distinct Dobble decks obtained from it by taking a perumtation of the $N^2+N+1$ symbols in the deck. If the permutation is an **automorphism** of the deck, we'll double-count the resulting deck, so the solution is obtained by dividing $(N^2+N+1)!$ by the size of the automorphism group for the corresponding projective plane, which for the relevant cases are $120960$ for $N=4$ and $49448448$ for $N=8$ (these numbers are well known, but can also be computed via a software package).

Solvers

• *Lazar Ilic (30/4/2024 3:47 PM IDT)
• *Bertram Felgenhauer (30/4/2024 8:32 PM IDT)
• *Yi Jiang (30/4/2024 8:34 PM IDT)
• *Daniel Copeland (1/5/2024 12:20 AM IDT)
• Paul Revenant (1/5/2024 2:24 AM IDT)
• Jingran Lin (1/5/2024 9:25 AM IDT)
• *Yan-Wu He (1/5/2024 5:51 PM IDT)
• *Alper Halbutogullari (3/5/2024 4:38 AM IDT)
• *Dejan Stakic (4/5/2024 1:29 PM IDT)
• *Sanandan Swaminathan (6/5/2024 12:41 PM IDT)
• *Hakan Summakoğlu (6/5/2024 10:44 PM IDT)
• Latchezar Christov (8/5/2024 12:15 PM IDT)
• *Guglielmo Sanchini (8/5/2024 3:42 PM IDT)
• Franciraldo Cavalcante (9/5/2024 4:36 AM IDT)
• Alex Fleischer (9/5/2024 2:26 PM IDT)
• *Guilliou Robin (9/5/2024 4:15 PM IDT)
• *Vladimir Volevich (10/5/2024 7:28 PM IDT)
• *King Pig (11/5/2024 2:10 AM IDT)
• Daniel Chong Jyh Tar (11/5/2024 11:28 AM IDT)
• Daniel Bitin (12/5/2024 1:59 AM IDT)
• Martin Thorne (13/5/2024 1:03 AM IDT)
• *Ward Beullens (13/5/2024 10:35 AM IDT)
• Arthur Vause (13/5/2024 10:46 AM IDT)
• *Ido Meisner (13/5/2024 6:05 PM IDT)
• *Asaf Zimmerman (13/5/2024 11:36 PM IDT)
• *Avi (14/5/2024 12:10 PM IDT)
• Sri Mallikarjun J (14/5/2024 7:15 PM IDT)
• Julian Ma (16/5/2024 3:46 AM IDT)
• *Dieter Beckerle (16/5/2024 7:37 AM IDT)
• *Victor Chang (17/5/2024 2:30 AM IDT)
• *Dan Ismailescu (17/5/2024 7:35 PM IDT)
• *Joaquim Carrapa (17/5/2024 9:56 PM IDT)
• Andrea Andenna (18/5/2024 6:22 PM IDT)
• Peter Huggins (20/5/2024 8:00 PM IDT)
• *David Greer (20/5/2024 8:29 PM IDT)
• Evan Semet (25/5/2024 8:38 AM IDT)
• Blaine Hill (27/5/2024 10:44 AM IDT)
• Gary M. Gerken (28/5/2024 1:48 AM IDT)
• Nyles Heise (28/5/2024 5:32 AM IDT)
• *Felipe Andrade (28/5/2024 4:30 PM IDT)
• *Marco Bellocchi (29/5/2024 1:39 AM IDT)
• Mark Pervovskiy (29/5/2024 10:43 PM IDT)
• Jason Kim (31/5/2024 3:26 AM IDT)
• *Karl Mahlburg (31/5/2024 5:39 AM IDT)
• Bert Dobbelaere (31/5/2024 10:35 PM IDT)
• *Motty Porat (31/5/2024 11:59 PM IDT)
• Benjamin Cha (2/6/2024 7:32 PM IDT)
• *Kang Jin Cho (3/6/2024 9:42 AM IDT)
• Rudy Cortembert (3/6/2024 7:41 PM IDT)
• Todd Will (4/6/2024 9:17 AM IDT)
• *Dan Dima (4/6/2024 3:20 PM IDT)
• Lorenz Reichel (4/6/2024 11:16 PM IDT)
• *Matt Cristina (5/6/2024 8:18 AM IDT)