What is the greatest possible number of sets

131 Views Asked by At

Let $X = \{1, 2, 3, . . . , 300\}$. A collection $F$ of distinct (not neccessarily non-empty) subsets of $X$ is lovely if for any three (not necessarily distinct) sets $A, B, C$ in $F$, at most three out of the following eight sets are non-empty: $$A \cap B \cap C, \overline{A} \cap B \cap C, A \cap \overline{B} \cap C, A \cap B \cap \overline{C}, \overline{A} \cap \overline{B} \cap C, A \cap \overline{B} \cap \overline{C}, \overline{A} \cap B \cap \overline{C}, \overline{A} \cap \overline{B} \cap \overline{C}, $$ where $\overline{S}$ denotes the set of all elements of $X$ that are not in $S$.
What is the greatest possible number of sets in a lovely collection?

My wrong attempt because $F$ is a set of subsets: First we prove that $|F| \leq 3$.
If $|F| \geq 4$ let $a, b, c, d \in F$. We consider $A=\{d, a\}$, $B=\{d, a\}$, $C=\{b, a\}$. Then $A \cap B \cap C, \overline{A} \cap \overline{B} \cap C, A \cap B \cap \overline{C}, \overline{A} \cap \overline{B} \cap \overline{C}$ are non-empty sets.

Let $|F|=3$, $F=\{a,b,c\}$ and $A,B,C$ subsets of $F$. If $A=B$ or $A=C$ or $B=C$ then we have $4$ empty intersections.

If $A\neq B\neq C\neq A$, we suppose that there exists $4$ non-empty intersections. By symetrry it's enough to verify $11$ cases and in each case two of them will be equal.

1

There are 1 best solutions below

2
On

Certainly |F| = 3 is possible: take F = {{1, ..., 100}, {101, ..., 200}, {201, ..., 300}} and note that any of the four intersections containing at least two non-negated members are empty, then note that the intersection of the complements is also empty. (The cases of choosing a set more than once is left as an exercise and is not hard.)

|F| = 4 is possible by adding in the empty set.

|F| = 5 is possible by adding in X. Note that at most two sets are nonempty if the empty set and X are both chosen.

I don't think |F| = 6 is possible, but I leave this to you!

So I'm suggesting F = {{}, {1..100}, {101..200}, {201..300}, {1..300}}. Of course there are lots of equivalent alternatives with 5 sets.