Solution Feb 12, 2012

Problem

Suppose X is a finite set such that | X | = 2k for some positive integer k. Suppose there's a family F of subsets of X, where each element of F has cardinality k, and such that every subset of X having cardinality k − 1 is uniquely contained in some element of F. Prove that k + 1 is prime.

Solution

Without loss of generality let X = \{1,2,\ldots, 2k \}. For a \geq 2, I claim that the number of sets in F containing S_a = \{1,2,\ldots, k-a\} is precisely \frac{(k+a)(k+a-1)\ldots(k+2)}{a!}.

There are 2k − (ka) = k + a numbers in XSa. Choosing any a − 1 numbers in XSa and including them in Sa will provide us with a subset of cardinality k − 1, which, by the condition on F, is uniquely contained in some set in F. There are clearly a! repetitions in creating a set in this manner, so the claim is proved.

Since \frac{(k+a)(k+a-1)\ldots(k+2)}{a!} is integer for all a \geq 2, it's now easy to see that k + 1 is prime.