Limit to Unique Combinations

Suppose you have a deck of cards. Each card has n images on it. Any two cards will have exactly one matching image. What would be the formula for the maximum number of unique images and the maximum number of unique cards?

At first I thought the maximum number of images would be:

$\sum\limits_{i=1}^n i$

But that doesn't seem right as the pairs themselves don't have to be unique (ie, you can have three cards that share a single image).

If $n$ is prime, one possibility is to take a projective plane over the field of $n$ elements for the underlying set of images, and then make one card for each line in the projective plane. Since every two lines intersect in exactly one point, you will have what you want.

The projective plane has $1+n+n^2$ points, and the same number of lines. So you could do it with this many images and cards. I don't know if this is maximal, though, or what to do if $n$ isn't prime.

(Have a look at http://en.wikipedia.org/wiki/Projective_plane if you don't know about projective planes.)

There are infinitely many cards with this property. Fix some picture which will appear on all cards, and make up $n-1$ new pictures for each card.

If the total number of pictures is $m$, then the Ray-Chaudhury-Wilson theorem implies that the maximal number of cards is $m$, assuming each card contains exactly $n$ pictures. Without that assumption, the Frankl-Wilson theorem states that the maximal number of cards is $m+1$.

I saw a game like this that had only two copies of any given image. In that case, for $n$ images per card you can have a deck of $n+1$ cards and need $\frac{n(n+1)}{2}$ unique images, as you said. I think the deck I saw had $n=8$.

I think for prime $p$ you can do it with $p^2+p$ images and $p^2$ cards, using $p+1$ images per card. For $p=3$ you have $$\begin{array}{ccc} 1ADG & 1CEH & 1BFJ \\ 2BEG & 2AFH & 2CDJ \\ 3CFG & 3BDH & 3AEJ \end{array}$$

I think the way to generalize this is to think of the cards as $(i,j)$ where $i$ and $j$ range from $0$ to $p-1$. You have $p$ sets of images, noted as $k$ ranging from $0$ to $p-1$ and each card gets image $i+jk \pmod {p}$ of set $k$ plus image $j$ of set $p$ (this is the one I forgot before)

As I am always one to like a cheap solution, you can do it with only one image. Think of the backs of a deck of cards.

• 1AD and 2BE don't intersect... – Yuval Filmus Feb 2 '11 at 3:26
• @Yuval: You are right. In fact none of the ones in a column intersect. So I can fix it easily – Ross Millikan Feb 2 '11 at 3:50