I saw a card game designed for small children. Each card has a picture of 6 animals on it, and there are 31 cards. When any two cards are compared to each other, they share exactly one animal. The game is for the child to find the animal that is common to both cards. I began to wonder how many animals the company would need to draw in order to produce such a set of cards.

So here's the question, more formally. Given N cards with K animals on each card, what is the minimum number of unique animals required such that there exists at least one collection of animals on cards where each card shares precisely one animal with each other card.

  • 1
    $\begingroup$ Keyword: combinatorial design. $\endgroup$ – David Richerby Sep 8 '15 at 16:27
  • 2
    $\begingroup$ I'm not sure there's any computer science content in this question. Migrating to Mathematics might be more appropriate. $\endgroup$ – David Richerby Sep 8 '15 at 16:28
  • 1
    $\begingroup$ Can you tell us why this is a computer science question? Why does this need a computer science perspective? Generally, pure math questions are off-topic here. We're not averse to math questions if they are best answered from a computer science perspective, but we expect you to explain in the question why a computer science perspective is needed/best. If you think this would be a better fit on Math.SE, flag it for moderator attention and we can migrate it for you. $\endgroup$ – D.W. Sep 8 '15 at 16:29
  • $\begingroup$ That's a good point. I was thinking of it like an algorithm question (was thinking I could approach it with Gray codes, or is finding such a set NP complete), but I suppose there's no reason it's not just a plain math question. I've moved it here: math.stackexchange.com/questions/1426916/… $\endgroup$ – Brandon Yarbrough Sep 8 '15 at 17:08
  • $\begingroup$ By the way: For future reference, instead of cross-posting a question, it's better to flag the original for moderator attention and ask the moderators to migrate it for you. We don't like to have multiple copies of the same question; each community should have an honest shot at answering without anybody's time being wasted. No big deal in this case -- I've taken care of it, so we're all good -- just letting you know for the future, so you know how to handle it if it ever comes up again. $\endgroup$ – D.W. Sep 9 '15 at 1:42

Browse other questions tagged or ask your own question.