Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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.)

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.