We first prove that ∣X∣>2n−2. In fact, if ∣X∣=2n−2, let X={1,2,…,2n−2}, B1={1,2}, B2={3,4}, …, Bn−1={2n−3,2n−2}. Since ∣Y∣=n, there exist two elements in Y that belong to the same Bi, then ∣Y∩Bi∣>1, a contradiction.
Let ∣X∣=2n−1.
Let B=⋃i=1nBi, then ∣B∣=2n−1−z, where z is the number of subset X∖B. Suppose the elements of X∖B are a1,a2,…,az.
If z≥n−1, take Y={a1,…,an−1,d}, and d∈B, as desired.
If z<n−1, suppose there are t elements that occur once in B1,B2,…,Bn. Since ∑i=1n∣Bi∣=2n, then
t+2(2n−1−z−t)≤2n,
it follows that t≥2n−2−2z. So the elements that occur twice or more than twice in B1,B2,…,Bn occur repeatedly by 2n−(2n−2−2z)=2+2z times.
Consider the elements that occur once in B1,B2,…,Bn:
b1,b2,…,bt. Thus, there are at most 22+2z=1+z subsets in B1,B2,…,Bn that do not contain the elements b1,b2,…,bt. So, there exist n−(z+1)=n−z−1 subsets containing at least the elements b1,b2,…,bt.
Suppose that B1,B2,…,Bn−1−z contain the elements b~1,b~2,…,b~n−1−z of b1,b2,…,bt, respectively. Since
2(n−1−z)+z=2n−2−z<2n−1,
there must exist an element d that is not in B1,B2,…,Bn−1−z but is in Bn−z,…,Bn.
Write Y={a1,…,az,b~1,b~2,…,b~n−1−z,d}, as desired.