Finding a bound for the number of cards in a deck

Question

A deck of cards is such that each card has $n$ images drawn inside it and such that each pair of cards has exactly one image in common, but no image is present on all the cards. The question is to find an upper bound $s(n)$ on the number of cards present in the deck.

I have thought of reformulating this problem in terms of finite geometry such that cards becomes lines and images become points so that two lines intersect at a point iff they both have the image associated to the latter. Unfortunately, I didn't manage to find a conclusive upper bound following this trail of thought. Any help would be very much appreciated.

Answer 1

Lemma: Each symbol occurs on at most $n$ cards.

I put the proof of this lemma behind a spoiler, in case you want to try figure this out yourself. Sometimes, knowing a smaller intermediary goal is enough to make the problem tractable.

Suppose the particular symbol $\star$ appears on $r$ cards. Let $C_1,C_2,\dots C_r$ be the cards on which $\star$ appears, and let $D$ be a card which does not contain $\star$. Then $D$ must contain one non-$\star$ symbol from each of $C_1,\dots,C_r$. Since the non-$\star$ symbols on $C_1,\dots,C_r$ are distinct, this means $D$ contains $r$ distinct symbols, so $r\le n$.

Now, consider a particular card, $L$. There are $n$ symbols on $L$, and for each symbol, our lemma implies there are at most $(n-1)$ cards besides $L$ which contain that symbol. This accounts for every card, since every card has exactly one symbol from $L$. Therefore, $$ s(n)\le 1+n\times (n-1)=n^2-n+1 $$ This bound is attainable if and only if a projective plane of order $n-1$ exists.