The making of "Spot It!": Finding almost unique sets Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, where the number of unique pictures in the deck is minimized.

Criteria: Fastest code for c = 31 and p = 6.

Inspiration: This puzzle was inspired by wondering how the makers of the card game Spot It! came up with a deck of cards that differ from each other by only one picture. If it helps, the game's instructions say it contains 31 cards with at least 30 unique pictures.

Brute-force reference implementation: (Entirely impractical for use at the scale of the contest judging criteria, but perhaps useful for thinking about the problem.)



class Program
{
    const int CardCount = 31, PicturesPerCard = 6;

    static void Main()
    {
        for (int pictureLimit = PicturesPerCard; ; ++pictureLimit)
            new Solver(pictureLimit).FindValidCards(0, 0);
    }

    class Solver
    {
        readonly byte[,] cards = new byte[CardCount, PicturesPerCard];
        readonly int pictureLimit;

        public Solver(int pictureLimit)
        {
            this.pictureLimit = pictureLimit;
        }

        public void FindValidCards(int c, int p)
        {
            for (; c &lt; CardCount; ++c) {
                for (; p &lt; PicturesPerCard; ++p) {
                    for (int picture = p == 0 ? 0 : cards[c, p - 1] + 1; picture &lt; pictureLimit; ++picture) { // Only consider pictures in numerically increasing sequence, since sequence order is irrelevant.
                        cards[c, p] = (byte)picture;
                        if (p &lt; PicturesPerCard - 1) {
                            FindValidCards(c, p + 1);
                        } else if (c &lt; CardCount - 1) {
                            FindValidCards(c + 1, 0);
                        } else if (AreCardsValid()) {
                            WriteCards();
                            System.Environment.Exit(0);
                        }
                    }
                }
            }
        }

        bool AreCardsValid()
        {
            for (int c = 0; c &lt; CardCount; ++c)
                for (int otherC = c + 1; otherC &lt; CardCount; ++otherC) {
                    int matchCount = 0;
                    for (int p = 0; p &lt; PicturesPerCard; ++p)
                        for (int otherP = 0; otherP &lt; PicturesPerCard; ++otherP)
                            if (cards[c, p] == cards[otherC, otherP])
                                ++matchCount;
                    if (matchCount != 1)
                        return false;
                }
            return true;
        }

        /// &lt;summary&gt;
        /// Writes to the console all the cards with each unique picture placed in its own column for easier comparison between cards.
        /// &lt;/summary&gt;
        void WriteCards()
        {
            for (int c = 0; c &lt; CardCount; ++c) {
                string cardString = string.Empty;
                for (int picture = 0; picture &lt; pictureLimit; ++picture)
                    for (int p = 0; ; ++p) {
                        if (p == PicturesPerCard) {
                            cardString += ' ';
                            break;
                        }
                        if (cards[c, p] == picture) {
                            cardString += (char)(picture &lt; 26 ? 'A' + picture : 'a' + (picture - 26));
                            break;
                        }
                    }
                System.Console.WriteLine(cardString);
            }
        }
    }
}


Edits: Reworded puzzle to correctly articulate the intent that the goal is to find a deck that matches the constraints. Added the missing constraint that no two pictures on a card may match. Changed contest type from code golf to speed.
This should be a comment rather than an answer, but it's not going to fit in a comment.

One way of looking at this problem is to flip it around:


  Given that you have N distinct pictures, what's the largest deck of cards you can build each of which has n distinct pictures such that the intersection of any two cards is precisely one picture?


Another way of phrasing this flipped-round problem is:


  What is the maximal size of binary code of length N, constant weight n and exact pairwise Hamming distance 2(n-1)?


This is bounded by the maximal size of binary codes of length N, constant weight n, and minimal Hamming distance 2(n-1). The best resource for such bounds appears to be http://www.win.tue.nl/~aeb/codes/Andw.html although some values here are extracted from OEIS (specifically A001839).

 N \ n  0   1   2   3   4   5   6   7   8   9
 0      1   -   -   -   -   -   -   -   -   -
 1      1   1   -   -   -   -   -   -   -   -
 2      1   1   1   -   -   -   -   -   -   -
 3      1   1   3   1   -   -   -   -   -   -
 4      1   1   3   1   1   -   -   -   -   -
 5      1   1   4   2   1   1   -   -   -   -
 6      1   1   5   4   1   1   1   -   -   -
 7      1   1   6   7   2   1   1   1   -   -
 8      1   1   7   8   2   1   1   1   1   -
 9      1   1   8   12  3   2   1   1   1   1
 10     1   1   9   13  5   2   1   1   1   1
 11     1   1   10  17  6   2   2   1   1   1
 12     1   1   11  20  9   3   2   1   1   1
 13     1   1   12  26  13  3   2   2   1   1
 14     1   1   13  28  14  4   2   2   1   1
 15     1   1   14  35  15  6   3   2   2   1
 16     1   1   15  37  20  6   3   2   2   1
 17     1   1   16  44  20  7   3   2   2   2
 18     1   1   17  48  22  9   4   3   2   2
 19     1   1   18  57  25  12  4   3   2   2
 20     1   1   19  60  30  16  5   3   2   2
 21     1   1   20  70  31  21  7   3   3   2
 22     1   1   21  73  37  21  7   4   3   2
 23     1   1   22  83  40  23  8   4   3   2
 24     1   1   23  88  42  24  9   4   3   3
 25     1   1   24  100 50  30  10  5   3   3
 26     1   1   25  104 52  30  13  5   4   3
 27     1   1   26  117 54  31  14  6   4   3
 28     1   1   27  121 63  33  16  8   4   3
 29     1   1   28  134 65  ?   20  8   4   3
 30     1   1   29  140 ?   ?   25  9   5   4
 31     1   1   30  155 ?   ?   31  9   5   4
 32     1   1   31  160 ?   ?   31  10  5   4


There are some easy to prove properties, but from what I've read so far it seems that in general there's no better method known than brute force.

Note that for n &gt; 2 these bounds appear to be loose for N &gt; n^2 - n + 1 (certainly they are for the values of n in the table above), and tight for N &lt;= n^2 - n + 1.

One useful result which handles the case that most interests you is as follows. (I could also write some code to wrap this up by using special cases and falling back to brute force, but I don't see the point).


  If N = n^2 - n + 1 then there is a nicely structured deck of N cards satisfying the required property.


The construction is quite simple:

(-1,-1) (x,0) (x,1) ... (x,n-2)                for x in 0..n-1
(0,y) (1,y+z % n-1) ... (n-1, y+(n-1)z % n-1)  for y in 0..n-2, z in 0..n-2


Each element appears in precisely n cards, which makes it optimal for decks in which more than one picture repeats.

Call the most frequent picture (selecting arbitrarily in case of a tie) f.

Lemma 1


  If f appears in more than n cards then it must appear in every card, and no other element repeats.


Proof: because each pairwise intersection contains precisely one element, all of the other elements in the cards containing f must be distinct. But then a card which doesn't contain f must have a non-trivial intersection with more than n disjoint sets despite having only n elements, which is impossible.

Corollary


  The largest possible deck in which f appears in more than n cards has size floor((N-1) / (n-1))


Excluding f from the N available pictures we get N-1 from which to draw disjoint sets of size n-1 to complete each card.

Lemma 2


  Any deck in which f appears in no more than n cards has at most n^2 - n + 1 cards.


Consider an arbitrary card containing f. By definition of f, none of the n elements of that card appears in more than n cards, and since each appears in that card the number of other cards is no more than n(n-1). Hence the deck cannot be larger than n(n-1) + 1.

Theorem


  The largest possible deck has an upper bound of max(n^2 - n + 1, floor((N-1) / (n-1))).


By combining the corollary and lemma 2.