# Create 55 sets with exactly one element in common

I have 55 sets $E_1, E_2,\cdots,E_{55}$

There are $n$ different elements.

Each set contains 8 elements $E_1\{x_1^1,x_1^2,x_1^3,x_1^4,x_1^5,x_1^6,x_1^7,x_1^8\}, E_2\{x_2^1,x_2^2,x_2^3,x_2^4,x_2^5,x_2^6,x_2^7,x_2^8\}\cdots$

If I take 2 sets randomly, they must have exactly one element in common, no more, no less.

How many elements do I have ? Is there more than one possibility ?

Actually I was playing a card game and I was curious about the mathematics behind.

Thanks!

EDIT: I'm looking for the lowest solution possible

• If you are curious about he mathematics behind Dobble, the keyword is "block designs". – Michal Adamaszek Jun 8 '18 at 13:34
• One solution is $386$, with one element in all the sets and the other $7\cdot 55=385$ elements distinct. – Ross Millikan Jun 8 '18 at 13:37
• @RossMillikan True, but it wouldn't be a very exciting card matching game :) – Bram28 Jun 8 '18 at 13:40
• Oh, indeed it's a solution. Then I'm looking for the lowest one. – tuxikigo Jun 8 '18 at 13:42
• There's some analog to fractional coloring. What is the fractional chromatic number of an 8-fold coloring of the complete graph on 55 vertices, with the added condition that any two vertices share exactly one color. – David Diaz Jun 8 '18 at 14:23

A lower bound is $n=57$. Take one set. It must have at least one element that it shares with at least seven other sets. Those eight sets all share one element, so all their other elements must be distinct. If there is an element shared $9$ ways $n$ must be at least $64$ because the other seven elements in each set need to be distinct.
There are $55\cdot 54/2=1485$ pairs of sets. An element that is in $8$ of the sets accounts for the match of $28$ pairs. An element that is in $7$ of them accounts for $21$ pairs. As both of these numbers are divisible by $7$ and $1485$ is not, there must be at least one element that is shared by a number other than $7$ or $8$.
As $1485 \equiv 1 \bmod 7$ and an element that is shared $6$ ways accounts for $15$ pairs, which is also equivalent to $1 \bmod 7$ I will guess that there is one element shared $6$ ways. We can then get the required number of pairs if there are $42$ elements shared $8$ ways and $14$ elements shared $7$ ways. This would give $n=57$.
We have not shown that this will work, but we can make a concrete example from the order $7$ projective plane. It has $57$ points, $57$ lines, with every two lines sharing a point and every two points sharing a line. The sets are the lines and the elements of each set are the points on it. We can discard two lines and get the required construction. Thanks to achillehui for pointing this out.
• the finite projective plane of order $7$ contains $57$ points and $57$ lines, each line contains $8$ points and two lines determine a point. – achille hui Jun 8 '18 at 15:02
• @Khoross: why? We could have the first nine sets contain element $1$ and the next eight contain element $2$. – Ross Millikan Jun 8 '18 at 17:31