A logic problem about set theory In a group of n people, subgroups with common interest are formed (football,tennis,snooker). The number of subgroups equals $2^{n-1}$. Any 3 subgroups have a common member. Prove that there is a person who is a member of all the subgroups.
proof by contradiction seems like a good fit here, but I can't seem to get the details right.
 A: Denote the set by $S,$ and let $X$ be the collection of subsets of $S$ as given in the problem. First note that $A\in X$ iff $A^{C}\notin X$ since we have exactly $1/2$ of the total number of subsets. From this we deduce that if $A, B\in X,$ then $A\cap B \in X,$ since $(A\cap B)^{C} \cap A\cap B = \emptyset.$ Now, if $\{x\} \in X$ for some singleton, then we're immediately done, so suppose this isn't true. Then every set of the form $S-\{x\}$ is in $X.$ Taking the intersection of two of these gives a set of the form $S-\{x, y\},$ and we clearly get all such sets. Continuing in this manner gives that every set is in $X,$ a contradiction, so we're done.
Alternatively you can just do this by induction on the intersection of $k$ sets, with the base case being $k=2$ proven above.
A: Given a finite set $N$ of size $n$, let $O_n$ be a family of subsets of $N$ such that any three elements of $O_n$ have non-empty intersection. Given that $|O_n| = 2^{n-1}$ you want to show that $\exists x \in N \forall o \in O_n : x \in o$. 
When forming an $O_n$, the maximum number of subsets of $N$ that can be chosen of a specific size $k$ is exactly the number of choices from $N$ where one element is fixed; this is exactly $\binom{n-1}{k-1}$. Fixing one choice ensures that all the subsets of size $k$ obey the requirement at any three subsets share an element.
Notice that enumerating the maximum choices for each $k \le n$ forms a row in Pascal's Triangle, and the sum of all the maximum counts for each $k$ is equal to $2^{n-1}$. Therefore, in order to form an $O_n$ whose cardinality is exactly $2^{n-1}$, the maximum number of each size $k$ subset must be chosen. This includes one singleton subset (if no singletons are chosen, then one more set must be chosen to reach the appropriate size, but one more choice from any other size subset would violate the maximum for that size). Thus, in order for $O_n$ to satisfy the requirement that any three subsets share an element, the fixed choice in each size $k$ subset must be the element of $N$ in the singleton.
Therefore the singleton choice is the $x$ that satisfies $\exists x \in N \forall o \in O_n : x \in o$
