Question

A collection of subsets of {1, . . . , n} has the property that each pair of subsets has at least one element in common. Prove that there are at most 2n−1 subsets in the collection

Answer 1

Here we Prove it by the Pigeonhole Principle as following type

let A'= {1, 2, . . . , n} A be its complement,for each set A.

Form the set of 2^n-1 pairs (A, A'). The reason why we have 2^n-1 such pairs is that each set has a unique complement and there are 2ⁿ subsets of our set {1, 2, . . . , n},

we take 2ⁿ/2 = 2^n-1

Suppose there were more than 2^n-1 ​​​​​​ subsets in the collection of subsets of {1, 2, . . . , n} with the property of that each pair of subsets has at least one element in common. That would mean, by the pigeon hole principle (the subsets are the pigeons and the pairs of subsets are the pigeonholes), that a subset and

its complement have been chosen.

This contradicts that each pair of subsets has at least one element
in common.

Hence proved

Please like??