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.


EDIT: I'm looking for the lowest solution possible

  • $\begingroup$ If you are curious about he mathematics behind Dobble, the keyword is "block designs". $\endgroup$ – Michal Adamaszek Jun 8 '18 at 13:34
  • 1
    $\begingroup$ One solution is $386$, with one element in all the sets and the other $7\cdot 55=385$ elements distinct. $\endgroup$ – Ross Millikan Jun 8 '18 at 13:37
  • $\begingroup$ @RossMillikan True, but it wouldn't be a very exciting card matching game :) $\endgroup$ – Bram28 Jun 8 '18 at 13:40
  • $\begingroup$ Oh, indeed it's a solution. Then I'm looking for the lowest one. $\endgroup$ – tuxikigo Jun 8 '18 at 13:42
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ If we can find an element in 9 different sets of the collection, the element must be in all sets in the collection - we have 9 sets which are all of unique elements bar the one shared element, hence cannot find a set of 8 elements which intersects all of these sets and does not contain the shared element. $\endgroup$ – Khoross Jun 8 '18 at 14:54
  • $\begingroup$ the finite projective plane of order $7$ contains $57$ points and $57$ lines, each line contains $8$ points and two lines determine a point. $\endgroup$ – achille hui Jun 8 '18 at 15:02
  • $\begingroup$ @Khoross: why? We could have the first nine sets contain element $1$ and the next eight contain element $2$. $\endgroup$ – Ross Millikan Jun 8 '18 at 17:31
  • $\begingroup$ @achillehui: Thanks much. That works. I found some arithmetic errors in what I had. $\endgroup$ – Ross Millikan Jun 8 '18 at 17:46

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.