Exercise 12, § 5

(a) Let $p$ and $q$ be two integers $\geqslant 1$, let $n = 2p + q$, let E be a set with $n$ elements, and let $N = \binom{n}{p} = \binom{n}{p+q}$. Let $(X_i)_{1 \leqslant i \leqslant N}$ (resp. $(Y_i)_{1 \leqslant i \leqslant N}$) be the sequence of all subsets of E which have $p$ (resp. $p + q$) elements arranged in a certain order. Show that there exists a bijection $\varphi$ of $[1, N]$ onto itself such that $X_{\varphi(i)} \subset Y_i$ for all $i$. (The method is analogous to that of Exercise 6 of § 4: observe that for each $r \leqslant N$ the number of sets $Y_j$ which contain at least one of $X_1$, $\ldots$, $X_r$ is $\geqslant r$.)

(b) Let $h$, $k$ be two integers $\geqslant 1$, let $n$ be an integer such that $2h + k < n$, let E be a set with $n$ elements and let $(X_i)_{1 \leqslant i \leqslant r}$ be a sequence of distinct subsets of E, each having $h$ elements. Show that there exists a sequence $(Y_j)_{1 \leqslant j \leqslant r+1}$ of distinct subsets of E, each having $h + k$ elements, such that each $Y_j$ contains at least one $X_i$ and each $X_i$ is contained in at least one $Y_j$ (by induction on $n$, using (a)).