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.

$\endgroup$
3
  • 3
    $\begingroup$ See, e.g., math.stackexchange.com/questions/36798/… and stackoverflow.com/questions/6240113/…. $\endgroup$
    – Ira Gessel
    Apr 24, 2014 at 23:52
  • 1
    $\begingroup$ For n=2k, exactly half of the sets are allowed or $\binom{n-1}{k}$. $\endgroup$ 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$ Apr 28, 2014 at 7:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.