RO-NMO 2004 Problem 94

Let $p,q \in \mathbb N^{\ast}$ , $p,q \geq 2$ . We say that a set $X$ has the property $\left( \mathcal S \right)$ if no matter how we choose $p$ subsets $B_i \subset X$ , $i = \overline{1,n}$ , not necessarily distinct, each with $q$ elements, there is a subset $Y \subset X$ with $p$ elements s.t. the intersection of $Y$ with each of the $B_i$ 's has an element at most, $i=\overline{1,p}$ . Prove that:

(a) if $p=4,q=3$ then any set composed of $9$ elements doesn't have $\left( \mathcal S \right)$ ;

(b) any set $X$ composed of $pq-q$ elements doesn't have the property $\left( \mathcal S \right)$ ;

(c) any set $X$ composed of $pq-q+1$ elements has the property $\left( \mathcal S \right)$ .

Dan Schwarz