S is a finite set with subsets S1, S2, ... , S1066 each containing more than half the elements of S. Show that we can find T ⊆ S with |T| ≤ 10, such that all T ∩ Si are non-empty.
Solution
Let |S| = n. Consider the number of pairs (x, X) with x ∈ S and X one of the 1066 subsets. There are > n/2 pairs (x, X0) for a given X0, and hence more than 533n in total. Hence there is an x1 which is in at least 534 subsets. That leaves ≤ 532 subsets. Each of these contains > n/2 elements of S - {x1}, so by the same argument we can find x2 so that the number of subsets not containing either x1 or x2 is at most 265. Similarly, we can find x3, so that at most 132 subsets do not intersect {x1, x2, x3}. Continuing, the sequence goes 65, 32, 15, 7, 3, 1, 0 for ten elements.
© John Scholes
jscholes@kalva.demon.co.uk
10 Dec 1999
Last corrected/updated 21 Nov 02