# Possible number of subsets that must intersect of $\{1,2,3,…100\}$ [duplicate]

$S$ be a collection of subsets of $\{1,2,3.....100\}$ such that the intersection of any two sets in $S$ is non-empty . What is the maximum possible cardinality $|S|$ of $S?$

$A.100$

$B.2^{100}$

$C.2^{99}$

$D.2^{98}$

Now one thing I can tell is that , *if all the subsets have cardinality $51$ or more then the property easily holds. So can I say $$\sum_{k=51}^{100} \binom{100}{k}$$ is a possible answer although it is not equal to any of the ones given in the options.

So, this is not the proper method. Then I thought there is another thing : whatever the cardinality , the subsets can be chosen in such a way that that they always intersect , with restrictions applying.

So, how do I approach the problem ,please show me a proper way.

Thanks.

## marked as duplicate by Leucippus, user223391, Rebecca J. Stones, Strants, Claude LeiboviciDec 20 '15 at 6:13

You can have all the subsets share one element, making $2^{99}$.

Suppose we have more that work. Then, we can remove subsets, until we have $2^{99}+1$ that work.

Define the $2^{99}$ pigeonholes by pairing subsets and their complement. Here, I demonstrate when we replace $100$ with $3$.

• $\{1, 2, 3\}, \{\}$
• $\{1, 2\}, \{3\}$
• $\{1, 3\}, \{2\}$
• $\{1\}, \{2,3\}$

Then by Pigeonhole Principle, since we have $2^{99}$ pigeonholes and $2^{99}+1$ pigeons, we have $2$ pigeons in a pigeonhole, so we have $2$ subsets, one the complement of the other. They do not intersect. Contradiction.

• I could not understand the pigeonholes logic . – user118494 Dec 19 '15 at 9:25
• I understand know. Thanks – user118494 Dec 19 '15 at 10:21