Let $ [n] = 1,\dots,n$ and $ P([n])$ denote the power set of $ [n]$. A subset $ S$ of $ P([n])$ is said to be good if for any $ A,B,C \in P([n]),\quad A\cap B\cap C$ is non empty. If $ A\in S$ then $ [n]\backslash A \notin S$. I shall prove that a good subset of $ P([n])$ of size $ 2^{n - 1}$ must contain a singleton. This is equivalent to prove that $ A_1\cap A_2 \dots A_{2^{n - 1}}$ is non empty where $ A_i$ are elements of a good subset of $ P([n])$. Let us on contrary assume that there exists a good subset of $ S$ of $ P([n])$ of size $ 2^{n - 1}$ and without a singleton. $ S$ contains all the subsets (of $ P([n])$) of cardinality $ n - 1$. Consider the fact $ \{1,2,\dots,n - 2,n - 1\}\cap\{1,2,\dots,n - 2,n\}\cap\{n - 1,n\} = \emptyset$ We can pair up every two subsets of size $ n - 1$ to conclude that $ S$ does not contain any subset of size $ n - 2$.( We can indeed go on to prove that if $ S$ contains all subsets of size $ r > \lfloor \frac {n}{2}\rfloor$ then it does not contain any subset of size $ n - r$) This would imply that $ S$ contains subsets of size $ n - 2$. (i) When $ n$ is odd. $ S$ contains all subsets of size $ r > \lfloor \frac {n}{2}\rfloor$. Though $ S$ contains $ 2^{n - 1}$ elements it is not good because $ \{1,2,\dots,\frac {n + 1}{2}\}\cap \{\frac {n + 1}{2},\dots,n\}\cap \{1,2\dots,\frac {n - 1}{2},\frac {n + 3}{2}\} = \emptyset$ (ii) When $ n$ is even. $ S$ contains all subsets of size $ > \lfloor \frac {n}{2}\rfloor$, $ |S| < 2^{n - 1}$. Therefore the assumption is false and a subset $ S$ with $ |S| = 2^{n - 1}$ contains a singleton.

very nice proof Srikanth! (you have a typo at line 7, should be doesnt contain subsets of size 2) and also in the even case $ S$ may also contain subsets of size $ \frac{n}{2}$ but it is easily ruled out by similar arguments.

I have a new solution: If X is one of the subsets, the complementar of X can not be in this family. So if X is not in the family => the complementar of X is in the family. ( because in total there are 2^n subsets and we have 2 ^(n-1) subsets => we must have one of this 2 subsets : x or complementar of x ) Let be A and B in the family. Because the complementar of the intersection of A and B can not be in the family (because it's intersection with A and B should be nonempty) => the intersection of A and B is in the family => by induction that the intersection of all the subsets must be in the family. So this intersection is non empty, because the empty subset can not be in the family.

Tell me if my solution is wrong Let $x_i=|\{j|i \in A_j\}|$ for $i=1,2,...,n$ Then we have $\sum_{i=1}^{n} \binom{x_i}{3}=\sum_{1 \leq i <j<k \leq 2^{n-1}}|A_i \cap A_j \cap A_k|$ Because $A_i \cap A_j \cap A_k$ is not empty for $i<j<k$,we have : $\sum_{i=1}^{n} \binom{x_i}{3} \geq \binom{2^{n-1}}{3}$ Let $M=max$ $x_i$ Then $n \binom{M}{3} \geq \binom{2^{n-1}}{3}$ => $nM(M-1)(M-2) \geq 2^{n-1}(2^{n-1}-1)(2^{n-1}-2)$ Suppose $M<n$,then $n^2(n-1)(n-2)>2^{n-1}(2^{n-1}-1)(2^{n-1}-2)$ Replace $n-1$ by $n$,we get the ineq: $(n+1)^2n(n-1) > 2^n(2^n-1)(2^n-2)$ =>$ n(n+1)(n^2-1) > (2^n-2)(2^n-1)2^n$ (*) We have the following ineq for $n \geq 2$ (1) $n \leq 2^n-2$ (2) $n^2-1 \leq 2^n$ (1) and (2) imply that (*) is impossible. So $M<n$ is wrong,implying that $M \geq n$ => $M=n$ => the intersection of all elements in $F$ is nonempty And we can check the problem for the case $n=1,2,3$,which is trivial.

Dear KDS,if we have $x_i<3$ for some i then we don't have the formula $\binom{x_{i}}{3}$ Am I wrong?

Love_Math1994 wrote: Dear KDS,if we have $x_i<3$ for some i then we don't have the formula $\binom{x_{i}}{3}$ Am I wrong? So then $\binom{x_i}{3}=0$ and that doesn't affect the proof

Let $\mathcal{F}_n$ be the family of all subsets of $[n]$. Let $\mathcal{F}_n(k)$ be the subfamily of elements of $\mathcal{F}$ that contain $k\in[n]$. Let the family in the problem be $\mathcal{G}$. Observe the natural poset isomorphism $\mathcal{F}_n(k)\cong \mathcal{F}_{n-1}$. Let $P_n$ be the partition of $\mathcal{F}_n$ into pairs of complements. Suppose that the claim is false; that for every $k\in[n]$, there is a $S\in\mathcal{G}$ so that $k\not\in S$. Clearly $\mathcal{G}$ has at most one element from each pair in $P_n$, and since there are $2^{n-1}$ pairs in $P_n$, $\mathcal{G}$ must have exactly one element from each pair. Consider the partition of $\mathcal{F}_n(k)$ induced by the natural poset isomorphism above and $P_{n-1}$ (call it $P_n(k)\cong P_{n-1}$). Note that each pair in $P_n(k)$ intersects to form the singleton $\{k\}$. But no two elements of $\mathcal{G}$ can intersect in a singleton; otherwise we can find by hypothesis some element of $\mathcal{G}$ not containing said singleton, and the intersection of these three sets is empty, a contradiction. So there are at most $2^{n-2}$ elements of $\mathcal{G}$ in any $\mathcal{F}_n(k)$. It follows that $\mathbb P_{S\in\mathcal{G}}(k\in S)\leqslant 0.5$, and by LoE we see that $\mathbb E_{S\in\mathcal{G}}(|S|)\leqslant 0.5 n$. Now partition $\mathcal{F}_n$ into families $K_0,K_1,\dots,K_n$ where $S\in K_i\iff |S|=i$. Note that if $S\in K_i$ then the element of $\mathcal{F}_n$ paired $S$ to by $P_n$ is in $K_{n-i}$. Finally, $\mathcal{G}\cap K_i$ must respect the Erdős-Ko-Rado Theorem when $i\leqslant 0.5n$, since there are no two sets in $\mathcal{G}$ with empty intersection. But $i<0.5n\implies \tfrac{\tbinom{n-1}{k-1}}{\tbinom{n}{k}}=\tfrac{k}{n}<0.5$, so $\mathbb E_{S\in\mathbb{G}}(|S|)>0.5n$, a contradiction $\blacksquare$ Remark: A bit overpowered, but oh well ¯\_(ツ)_/¯

Induct on $n$.For $n=2$ if follows right away.Suppose it holds for $n$ let's prove it for $n+1$.Brake all the subsets of $[n+1]$ is two sets;one that contaion $n+1$ say $A_{n+1}$ and the ones that don't say $B$.Now if $\mid B\mid \geq 2^{n-1}$ by induction we're done immediately ,so suppose $|A_{n+1}|>2^{n-1}$.Consider set $C$ obtained from $A_{n+1}$ by throwing out $n+1$ from each set.Now we have a family of more that half subets of $[n]$ and hence in a such family we have a set and its complement say $S,S'$.Now obviously $S\cap S'=\{\}$ and hence by using the triple $(S'\cup n+1,S\cup n+1,X)$ $\forall X\in B$ we have that all elements of $B$ contain $n+1$ a contradiction and hence the desired.

rafayaashary1 wrote: Let $\mathcal{F}_n$ be the family of all subsets of $[n]$. Let $\mathcal{F}_n(k)$ be the subfamily of elements of $\mathcal{F}$ that contain $k\in[n]$. Let the family in the problem be $\mathcal{G}$. Observe the natural poset isomorphism $\mathcal{F}_n(k)\cong \mathcal{F}_{n-1}$. Let $P_n$ be the partition of $\mathcal{F}_n$ into pairs of complements. Suppose that the claim is false; that for every $k\in[n]$, there is a $S\in\mathcal{G}$ so that $k\not\in S$. Clearly $\mathcal{G}$ has at most one element from each pair in $P_n$, and since there are $2^{n-1}$ pairs in $P_n$, $\mathcal{G}$ must have exactly one element from each pair. Consider the partition of $\mathcal{F}_n(k)$ induced by the natural poset isomorphism above and $P_{n-1}$ (call it $P_n(k)\cong P_{n-1}$). Note that each pair in $P_n(k)$ intersects to form the singleton $\{k\}$. But no two elements of $\mathcal{G}$ can intersect in a singleton; otherwise we can find by hypothesis some element of $\mathcal{G}$ not containing said singleton, and the intersection of these three sets is empty, a contradiction. So there are at most $2^{n-2}$ elements of $\mathcal{G}$ in any $\mathcal{F}_n(k)$. It follows that $\mathbb P_{S\in\mathcal{G}}(k\in S)\leqslant 0.5$, and by LoE we see that $\mathbb E_{S\in\mathcal{G}}(|S|)\leqslant 0.5 n$. Now partition $\mathcal{F}_n$ into families $K_0,K_1,\dots,K_n$ where $S\in K_i\iff |S|=i$. Note that if $S\in K_i$ then the element of $\mathcal{F}_n$ paired $S$ to by $P_n$ is in $K_{n-i}$. Finally, $\mathcal{G}\cap K_i$ must respect the Erdős-Ko-Rado Theorem when $i\leqslant 0.5n$, since there are no two sets in $\mathcal{G}$ with empty intersection. But $i<0.5n\implies \tfrac{\tbinom{n-1}{k-1}}{\tbinom{n}{k}}=\tfrac{k}{n}<0.5$, so $\mathbb E_{S\in\mathbb{G}}(|S|)>0.5n$, a contradiction $\blacksquare$ Remark: A bit overpowered, but oh well ¯\_(ツ)_/¯ I am sure your solution is beautiful, but I kind of don't understand the notations. $\mathbb{P}(k\in S)$ means the probability of choosing a set $S$ that contains $k$. "LoE" is " lnearity of expectation I guess, $\mathbb{E}(|S|)$ is the expectation of the cardinality of $S$ ? and why $\mathbb{P}(k\in S)\leq 0.5\Rightarrow \mathbb{E}(|S|)\leq 0.5n$.

Because by LoE we have $\mathbb E(|S|)=\sum_{k\in [n]}\mathbb P(k\in S)\cdot 1$

nikolapavlovic's solution motivates another approach: Consider the vertices of the Boolean Lattice $B_n$ where the elements are the subsets of $[n]$. Connect vertices $v_1,v_2$ if they are complementary sets or if there exists an element $k\in v_1,v_2$ and $v_i\setminus \{k\}$ and $v_2\setminus\{k\}$ are complementary with respect to $[n]\setminus \{k\}$. Effectively we have to choose $2^{n-1}$ vertices so that there is exactly one in every edge (we can show that each $k$ is contained in exactly one-half of the sets, and then it follows by pigeonholes). So it suffices to find an odd cycle in our graph. Actually we can do it and prove it by accounting for each digit in the representative binary string as in this image. In the diagram $l_k$ is the natural complement (if it exists) wrt to the singleton $\{k\}$, and $u$ is the universal complement map.

$\textbf{Proof :}$ If sets $X$ and $[n]\setminus X$ lies in $\mathcal{F}$ then we get obvious contradiction. So from $|\mathcal{F}|=2^n/2$ we get that for any $X\in\mathcal{F}$, $[n]\setminus X\notin \mathcal{F}$. Also true reverse : for any $X\notin\mathcal{F}$, $[n]\setminus X\in \mathcal{F}$. So easy to check that if $X, Y\in\mathcal{F}$, then $\emptyset\not= X\cap Y\in\mathcal{F}$. Let $W$ be minimal set in $\mathcal{F}$, so for every $X\in\mathcal{F}$, $W\cap X\in\mathcal{F}$ and so $W\subseteq X$. $\Box$

The follow up question is: what is the minimum size of $\mathcal{F}$ such that the property given in the original problem still holds. There is a lower bound: $|\mathcal{F}| \ge 5\times 2^{n-4} + 1$ for $n\ge 4$. For example: $\mathcal{F}'$ is collection of all subsets of the form $A\cup B$ with $A$ is a subset of at least 3 elements of $\{1, 2, 3, 4\}$ and $B$ is subset of $\{5, ..., n\}$. Then $|\mathcal{F}'| = 5\times 2^{n-4}$ and any three elements of $\mathcal{F}'$ has a common element but all elements of $\mathcal{F}'$ don't have a common element. For $n = 4$, then the lower bound is tight. That is any collection of at least $6$ subsets of $\{1, 2, 3, 4\}$ with any three of them having non-empty intersection. then all of them have non-empty intersection.

Sorry for very poorly written solution. I was writing it up as I was solving it. The idea is to use the following lemma: Lemma: Let $F$ be a family of subsets of $S$ such that for any $X,Y \in F$ satisfy that $X\cap Y$ is not empty. Then $ |F| \leq 2^{n - 1}$. Proof: We can match the subsets on pairs $(X, S-X)$ so $|F\cap (X, S-X)| \leq 1$ this implies the lemma. $\square$ The family $F$ satisfy the Lemma so the equality occurs so always $|F\cap (X, S-X)| = 1$ for any $X \in S$. If exists $A,B \in F$ such that $|A\cap B|=1$ then for any $C \in F$ we have that $|A\cap B\cap C|=1$ and $(A\cap B) \subset C$ this implies the problem. Then if $A \in F \implies S-a \not \in F$, but if $v \in A$ then $|A\cap \{(S-A)\cup \{v\}\}|=1$ so by FTSOC $(S-A)\cup \{v\} \not \in F$ By the equality of the lemma we have that $A-\{v\} \in F$, if we suppose that $ |A|$ is minimum this give us a contradiction. $\blacksquare$