Between us my sister and I know everything -- how many sisters do I have?

Question

My name is Aaron. I used to think my twin brother Bernard and I were pretty smart. You see between us, we know everything.

That was until we met the triplets Charlotte, Denise, and Esther. Between any two of the sisters, they knew everything.

I asked Charlotte did she know are there any quadruplets or quintuplets who, between any pair, know everything. She doesn't know but that means we can ask Denise or Esther when we see them next. Unfortunately they are on holiday in Fiji. So I will ask the internet instead.

Problem: Suppose we have a set $F=\{1,2,\ldots, n\}$ of facts. Consider a family (haha, family) $\{F_1,\ldots, F_m\}$ of distinct subsets of $F$ where $F_i \neq F_j$ for $i\neq j$, i.e., each $F_i$ is distinct. We call the family knowledgeable to mean that for any distinct $F_i,F_j$ we have $F_i \cup F_j = F$. What is the largest cardinality of a knowledgeable family?

The answer is at least $n+1$, since you can have sets $F_i = F \setminus \{i\}$ and $F_{n+1}=F$.

Is the answer exactly $n+1$?

Answer 1

This problem is well-suited for the pigeonhole principle. Assume there are $n+2$ people. Possibly, one of these people knows all of the facts; we set this person aside, leaving at least $n+1$ people.

Each person is a pigeon. Each fact has a corresponding hole. Each person is placed into a pigeonhole corresponding to a fact they do not know. If a person does not know several facts, they choose one arbitrarily, and place themselves in that hole.

There are $n+1$ pigeons in $n$ holes. Some hole must have two pigeons, but this would mean there was a fact that was unknown by two people, so those two people do not know all the facts. Therefore, when we add back in the know-it-all set aside at the beginning any successful family can have at most $n+2$ people.

Answer 2

Let $\mathcal F$ be a knowledgeable family. Let $I = F \setminus \bigcap \mathcal F$.

For each $i \in I$ we have $i \notin \bigcap \mathcal F$. So we have $i \notin F_i$ for some $F_i \in \mathcal F$.

We claim $\mathcal F \subset \{F\} \cup \{F_i: i \in I\}$.

Let $G \in \mathcal F\setminus \{F\}$ be arbitrary. We have $j \notin G$ for some $j \in I$. Since we must have $G \cup F_j = F$ and both sets exclude $j$, the two sets must coincide.

So there is at most one element of $\mathcal F$ for each element of $I$. So there are at most $n$ proper elements of the family, plus one if $F$ itself is a member of the family.

It follows the largest family has $\bigcap \mathcal F = \varnothing$.