(a) is a consequence of (b) and (b) is almost obvious: we partition the set into
parts of size
, and take these to be
of the sets, while the
'th set is just equal to one of the first
. No matter how we choose
elements, some two of them will be in the same part in our partition, and we're done.
For (c), we can use induction on
. For
has
elements, and we choose two subsets
of size
of
. If
don't cover
, then we choose one of our elements to be outside both
, and the second element arbitrarily, and if they do cover
, we take the first element in
, and the second one in
, which are clearly both non-empty.
Suppose now that (c) has been proven for values smaller than our current
, which we assume to be
. Let's count the pairs
, where
and
is one of the
sets which contains
. On the one hand, this count gives
, because there are
's and each of them has
elements. On the other hand, it's
, where
is an enumeration of the elements of
, and
is the number of sets among the
chosen ones that contain
. Since
, there is at least one
with
. We take this
to be one of the chosen elements of
, and eliminate the
elements of one of the
chosen subsets of
as follows: if
belongs to no such set, this set will be arbitrary, while if it does belong to such a set, we eliminate precisely this (unique, because
) set. We are now in the same setting as before, except that now
has been replaced by
, and the induction hypothesis gives us the extra
elements of
that we have to choose.
