2
$\begingroup$

$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.

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.