Let be an integer greater than and let be a finite set containing more than elements. Consider the collection of all sets of subsets of satisfying the following two conditions:
(a) Each member of contains at least elements of ; and
(b) Each element of is contained in at least members of .
Determine , as runs through all subsets of whose members cover , and runs through the above collection.
Solution
The required number is . We begin by showing that any set of subsets of satisfying the two conditions in the statement has a subcover of cardinality at most .
This is clear if is a member of .
Assume henceforth that does not contain . If some member of has more than elements, for each element of choose a containing member of . The latter along with form a subcover of of cardinality .
Assume henceforth that each member of has exactly elements. Fix a member of .
If some member of contains more than one element of , for each element of choose a containing member of . The latter along with and form a subcover of of cardinality .
Finally, if no member of contains more than one element of , write , choose a member of containing and notice that is a singleton set, say . Since is contained in at least members of , each of which contains (exactly) elements of , we may choose a member of containing both and (recall that ). If , continue choosing members of containing , , to form an -element subcover of consisting of .
To complete the proof, we produce a set of subsets of satisfying the two conditions in the statement, no subcover of which has less than members. To this end, write , , and let be the -element subsets of the upper part of . The sets , , , satisfy both conditions in the statement and at least of them are needed to cover . (The condition is required for an element in the upper part to lie in at least of these sets.)