0
$\begingroup$

This question was triggered by the game Spot It!.

The game consists of cards, each having $k$ different symbols from an alphabet of $n>k$ symbols, with the property that any 2 cards have at least one symbol in common. This lead to a natural question: what is the maximal number $N(n,k)$ of different Spot It! cards?

It follows from pigeon-hole principle that for $n<2k$ the card deck can contain the complete set of $$\frac{n!}{k!(n-k)!}$$ possible choices of $k$ symbols out of the alphabet of $n$. I couldn't get the answer for $n\ge 2k$ so far.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ See, e.g., math.stackexchange.com/questions/36798/… and stackoverflow.com/questions/6240113/…. $\endgroup$
    – Ira Gessel
    Commented Apr 24, 2014 at 23:52
  • 1
    $\begingroup$ For n=2k, exactly half of the sets are allowed or $\binom{n-1}{k}$. $\endgroup$
    – The Masked Avenger
    Commented Apr 25, 2014 at 1:42
  • 1
    $\begingroup$ In the actual card game, any two distinct cards have exactly one symbol in common. This is Ray Chaudhuri-Wilson (as mentioned in the stackedchange solution). Your variation, in which any two cards have at least one symbol in common, connects with the Erd\H{o}s-Ko-Rado theorem. Masked Avenger's answer, which I'll rewrite as $\binom{n-1}{k-1}$, is the maximum for all $n \ge 2k$. $\endgroup$
    – Peter Dukes
    Commented Apr 28, 2014 at 7:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .