Partitions that separate all subsets
I brute forced with $n$ going from 2 to 8. The minimum $k$ for those $n$ were $1,2,2,3,3,4,4$. I looked at the minimal set of partitions, and noticed that they could be constructed like this:
- Let the 1st set of the 1st partition be
$\{\lfloor n/2\rfloor ,...,1\}$ - To get the 1st set of the 2nd partition change the 1st value to the smallest unused value $\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor-1,...,1\}$
- To get the 1st set of the 3rd partition change the 2nd value to the smallest unused value
$\{\lfloor n/2\rfloor+1 ,\lfloor n/2\rfloor+2,\lfloor n/2\rfloor-2,...,1\}$
and continue until you have the first set of $\lfloor (n+1)/2\rfloor$ partitions. The other sets must be complements to the first ones.
Using this construction I continued for $n=9,...,22$, and found that $5,5,6,6,7,7,8,8,9,9,10,10,11,11$ partitions suffice. However for these $n$ I didn't brute force to confirm minimality. I know this is no answer until I have a proof for the sufficiency of $\lfloor (n+1)/2\rfloor$
$\def\FF{\mathbb{F}}$ The construction of lasen H is optimal.
Suppose that we have $k$ partitions with the desired property. We encode these partitions as vectors $\vec{v}_1$, $\vec{v}_2$, ..., $\vec{v}_k \in \FF_2^n$ where we put a $1$ in the $j$-th coordinate of $\vec{v}_i$ if $j$ is in the first part of the $i$-th partition. We also set $\vec{v}_0 = (1,1,\ldots, 1)$.
Define the subspace $W$ of $\FF_2^n$ by $$W = \{ \vec{w} : \vec{v}_0 \cdot \vec{w} = 0 \ \mbox{and} \ \vec{v}_1 \cdot \vec{w} = \vec{v}_2 \cdot \vec{w} = \cdots = \vec{v}_k \cdot \vec{w} \}.$$ Since $W$ is defined by $k$ linear equations, $\dim W \geq n-k$. Define the quadratic form $Q$ on $\FF_2^n$ by $Q(x_1, x_2, \ldots, x_n) = \sum_{i<j} x_i x_j$.
Now, let $\vec{w} \in W$ and let $B = \{ j : \vec{w}_j =1 \}$. Since $\vec{v}_0 \cdot \vec{w} = 0$, the size of $B$ is even, say $B = 2m$. There is supposed to be some partition $(X_i, Y_i)$ where $|X_i \cap B| = |Y_i \cap B|$. For this $i$, we have $\vec{v}_i \cdot \vec{w} = m$. By the defining equations of $W$, we also have $\vec{v}_1 \cdot \vec{w} = m$.
We also have $Q(\vec{w}) = \binom{2m}{2} \equiv m \bmod 2$. So $Q(\vec{w}) = \vec{v}_1 \cdot \vec{w}$ for all $\vec{w} \in W$.
We therefore deduce, for $\vec{x}$ and $\vec{y}$ in $W$, that $Q(\vec{x}+\vec{y}) = Q(\vec{x}) + Q(\vec{y})$. Writing $\vec{x} = (x_1, \ldots, x_n)$ and $\vec{y} = (y_1, \ldots, y_n)$, we have $$0 = \sum_{i<j} {\Big (} (x_i+x_j)(y_i+y_j) - x_i x_j - y_i y_j {\Big )} = \sum_{i<j} (x_i y_j + x_j y_i) = \sum_{i \neq j} x_i y_j$$ $$= \left( \sum_i x_i \right) \left( \sum_j y_j \right) - \sum_r x_r y_r = (\vec{v}_0 \cdot \vec{x}) (\vec{v}_0 \cdot \vec{y}) - \vec{x} \cdot \vec{y}$$ for all $\vec{x}$, $\vec{y} \in W$. But, for $\vec{x} \in W$ we have $\vec{x} \cdot \vec{v}_0 =0$. So we deduce that $\vec{x} \cdot \vec{y} =0$ for $\vec{x}$ and $\vec{y} \in W$.
In other words, $W \subseteq W^{\perp}$, so $\dim W \leq n - \dim W$. Combined with $\dim W \geq n-k$, we have $n-k \leq n-(n-k)$ so $n/2 \leq k$. Since $k$ is an integer, we can improve this to $\lceil n/2 \rceil \leq k$, which is lasen H's bound.
We can prove a lower bound of order $\sqrt{n}$. Let $\mathcal{A}_i$ be the pair $(X_i, Y_i)$ and set $|X_i| = x_i$ so $|Y_i| = n - x_i$.
Lemma There are precisely $\binom{n}{x_i}$ subsets $B$ of $[n]$ such that $|B \cap X_i| = |B \cap Y_i|$.
Proof We biject these sets $B$ with the subsets $C$ of $[n]$ of cardinality $x_i$. Specifically, $B \mapsto (X_i \setminus B) \cup (Y_i \cap B)$. $\square$
You want each of the $2^{n-1}$ even subsets of $[n]$ to occur as such a $B$ for at least one index $i$. Therefore, $$2^{n-1} \leq \sum_i \binom{n}{x_i}.$$ We have $\binom{n}{x_i} \leq 2^n/\sqrt{\pi n/2}$ (see here for a similar bound) so there must be at least $\sqrt{\pi n/8}$ terms in the sum.