Let $ X$ be a set containing $ 2k$ elements, $ F$ is a set of subsets of $ X$ consisting of certain $ k$ elements such that any one subset of $ X$ consisting of $ k - 1$ elements is exactly contained in an element of $ F.$ Show that $ k + 1$ is a prime number.
Problem
Source: Chinese TST 2009 4th P3
Tags: combinatorics proposed, combinatorics
06.04.2009 01:37
It is also Indian TST 1998, apparently: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=195941 (I found this by searching for "subsets prime" (without quotes) in the Combinatorics forums.) Also, the converse is on the forum (but no responses yet): http://www.artofproblemsolving.com/Forum/viewtopic.php?t=253058
03.06.2010 00:45
It is a topic of combinatorial Design Theory. When each $(k-1)$-set is included in one and only one block of the family, it follows that for any value $1\leq a\leq k-1$, each $a$-set is included in a same number of blocks. This is easily computed: there are $\binom {2k-a} {k-1-a}$ $(k-1)$-sets containing a given $a$-set; each block containing the $a$-set contains $\binom {k-a} {k-1-a} = k-a$ of those $(k-1)$-sets, therefore there are exactly $\frac {1} {k-a} \binom {2k-a} {k-1-a}$ such blocks. In particular, for $k\geq 3$, we have a $(v,b,k,r,\lambda)$-BIB, with $v=2k$, $b = \frac {1} {k+1} \binom {2k} {k}$, $r = \frac {1} {k+1} \binom {2k-1} {k}$, $\lambda = \frac {1} {k+1} \binom {2k-2} {k}$. It means $k-a$ divides $(2k-a)(2k-a-1)\cdots (k+2)$ for all $1\leq a \leq k-2$, including all the primes $p=k-a$ in the range $2\leq p \leq k-1$, therefore none can divide $k+1$, hence the latter is a prime. The converse requires the existence of such highly symmetric designs (there is a vast literature related), and this is not the case for all primes. Little is known on which work.