PS: For a subset of A, A' is the set of all elements which are not element of the set A, but element of the set E.

Call a family of subsets of $E$ good if it satisfies the conditions. First, observe that the symmetry of the rules means that if $\{A_1, \ldots, A_k\}$ is a good family, we can replace any $A_i$ with $A_i'$ and the family will still be good. A good family cannot contain two identical sets, sets which are complements of each other (wrt $E$), $\emptyset$, or $E$ (unless it contains just that subset and no others.) So, for every set in a family satisfying the conditions, we can replace it with its complement if it contains $n$, so no set contains $n$. Now, $A_i' \cap A_j'$ will never be $\emptyset$ for any $i < j$. Thus, one of the other intersections is the nullset. We can see that this means that for $A_i$ and $A_j$, either one strictly contains the other or they are disjoint. Sort the sets by increasing cardinality, so $|A_i| \leq |A_j|$ if $i \leq j$. Consider subfamilies $F_m = \{A_1, A_2, \ldots, A_m\}$ (with $F_0 = \emptyset$). Let $S_m = A_1 \cup A_2 \cup \cdots \cup A_m$; let $B_m$ be the family of subsets $A_i$ that are not contained in any other subset in $F_m$ (thus, all the subsets in $B_m$ are disjoint). Let $x_m = 2|S_m| - |B_m|$. Claim: $x_m < x_{m+1}$ for $1 \leq m < k$. Proof: Case 1: $S_m = S_{m+1}$. Then, $A_{m+1} \subset S_m$. Since for each $A_i \in B_m$, it is either disjoint with or completely contained in $A_{m+1}$, we know that $A_{m+1}$ must be the union of some subsets in $B_m$. Also, at least two subsets must be involved or $A_{m+1}$ would just be identical to a previous subset. Thus, $B_{m+1}$ will contain $A_{m+1}$ but not the subsets it's a union of, and $|B_{m+1}| < |B_m|$, so $x_m < x_{m+1}$. Case 2: $|S_m| < |S_{m+1}|$. Then $B_{m+1}$ can only contain one subset not in $B_m$, namely $A_{m+1}$. Thus, $|B_{m+1}| \leq |B_m| + 1$, so $x_{m+1} \geq 2(|S_m| + 1) - (|B_m| + 1) = 1 + x_m$ so $x_{m+1} > x_m$. Thus, the claim is proved. $x_0 = 0$ and $x_k = 2|S_k| - |B_k| \leq 2(n-1) - (1) = 2n-3$, so $k \leq 2n-3$. This bound is reachable; let $A_i = \{i\}$ for $1 \leq i \leq n-1$ and $A_{n-2+i} = \{1, 2, \ldots, i\}$ for $2 \leq i \leq n-1$. Thus, the answer is $\boxed{2n-3}$.

math_explorer wrote: Call a family of subsets of $E$ good if it satisfies the conditions. First, observe that the symmetry of the rules means that if $\{A_1, \ldots, A_k\}$ is a good family, we can replace any $A_i$ with $A_i'$ and the family will still be good. A good family cannot contain two identical sets, sets which are complements of each other (wrt $E$), $\emptyset$, or $E$ (unless it contains just that subset and no others.) So, for every set in a family satisfying the conditions, we can replace it with its complement if it contains $n$, so no set contains $n$. Now, $A_i' \cap A_j'$ will never be $\emptyset$ for any $i < j$. Thus, one of the other intersections is the nullset. We can see that this means that for $A_i$ and $A_j$, either one strictly contains the other or they are disjoint. Sort the sets by increasing cardinality, so $|A_i| \leq |A_j|$ if $i \leq j$. Consider subfamilies $F_m = \{A_1, A_2, \ldots, A_m\}$ (with $F_0 = \emptyset$). Let $S_m = A_1 \cup A_2 \cup \cdots \cup A_m$; let $B_m$ be the family of subsets $A_i$ that are not contained in any other subset in $F_m$ (thus, all the subsets in $B_m$ are disjoint). Let $x_m = 2|S_m| - |B_m|$. Claim: $x_m < x_{m+1}$ for $1 \leq m < k$. Proof: Case 1: $S_m = S_{m+1}$. Then, $A_{m+1} \subset S_m$. Since for each $A_i \in B_m$, it is either disjoint with or completely contained in $A_{m+1}$, we know that $A_{m+1}$ must be the union of some subsets in $B_m$. Also, at least two subsets must be involved or $A_{m+1}$ would just be identical to a previous subset. Thus, $B_{m+1}$ will contain $A_{m+1}$ but not the subsets it's a union of, and $|B_{m+1}| < |B_m|$, so $x_m < x_{m+1}$. Case 2: $|S_m| < |S_{m+1}|$. Then $B_{m+1}$ can only contain one subset not in $B_m$, namely $A_{m+1}$. Thus, $|B_{m+1}| \leq |B_m| + 1$, so $x_{m+1} \geq 2(|S_m| + 1) - (|B_m| + 1) = 1 + x_m$ so $x_{m+1} > x_m$. Thus, the claim is proved. $x_0 = 0$ and $x_k = 2|S_k| - |B_k| \leq 2(n-1) - (1) = 2n-3$, so $k \leq 2n-3$. This bound is reachable; let $A_i = \{i\}$ for $1 \leq i \leq n-1$ and $A_{n-2+i} = \{1, 2, \ldots, i\}$ for $2 \leq i \leq n-1$. Thus, the answer is $\boxed{2n-3}$. I don't think it's true becuse you didn't thougt one part: if $A_i \cup A_j =E and E-A_i \neq A_j$ .

Qmer_Kacha wrote: I don't think it's true becuse you didn't thougt one part: if $A_i \cup A_j =E$ and $E-A_i \neq A_j$ . $A_i \cup A_j =E$ cannot happen once we perform the step: Quote: So, for every set in a family satisfying the conditions, we can replace it with its complement if it contains $n$, so no set contains $n$.