Interpret the sets $A,B$ as $\ell$-vectors in $(\mathbb{Z}/2\mathbb{Z})^\ell$ (where $\ell\ge n+1$ is the number of distinct elements in the union of the sets). Now this is a simple application of the CNS to restricted sumset problems. (In full generality, Theorem 5.1 here.) Edit: For more computational descriptions, see this.

This is exactly the problem from Saint Petersburg selection tests to the All-Russian olympiad of year 2006. It was proposed by Dima von der Flaass (who passed away year ago) and solved by Max Alekseev here.

I cannot read Russian. Can you post the solution here, please?

Idea is to fix some element $s$ and partition the families $B,R$ of blue and red sets onto subfamilies $B_+,B_-$; $R_+,R_-$ (containing $s$ and not containing $s$.) Assume that $|B_+|+|R_+|>2^{n-1}$ and both $B_+,R_+$ are non-empty, or the same with $B_-,R_-$. Then our symmetric differences have at least $2^n$ subsets not containing $s$ (induction in $n$, apply induction proposition to $B_+,R_+$). Analogously, if $|B_+|+|R_-|>2^{n-1}$ and both $B_+,R_-$ are non-empty, then our symmetric differences have at least $2^n$ subsets containing $s$; the same with $B_-,R_+$. So, if all $B_+,B_-,R_+,R_-$ are non-empty, we are done. How to find such element $s$? If all symmetric differences are distinct, there are $|B|\cdot |R|\geqslant 2^n$ of them. If two symmetric differences coincide, say, $b_1\Delta r_1=b_2\Delta r_2$ for $b_1,b_2\in B$, $r_1,r_2,\in R$, then $b_1\Delta b_2=r_1\Delta r_2$ and any element $s\in b_1\Delta b_2$ works.

Oh, I got it. Thanks for the solution.

Here's an approach which mimics the combinatorial proof of the Cauchy-Davenport theorem, with a slight change at the end. Interpret each set as a binary string corresponding to some integer in the obvious way, and let $\oplus$ denote the binary XOR operation. Let $A,B$ be the sets of red and blue sets; our goal is to show $|A\oplus B| \ge 2^n$, when $|A|+|B|=2^n+1$. WLOG assume $|A| \ge |B|$. We'll prove the more general result that if $2^n < |A|+|B| \le 2^{n+1}$, then $|A\oplus B| \ge 2^n$, and we'll also allow $A,B$ to have nonempty intersection. To do this we'll perform the following algorithm: First replace $B$ with the set $B'=B \oplus \{c \}$ for some nonnegative integer $c$ to be chosen later. We'll choose $c$ in such a way that $|B|> |A \cap B'| > 0$. Clearly this preserves the size of the sumset $|A\oplus B|$ due to the associativity of $\oplus$. Now we can replace $A$ with $A \cup B'$ and $B$ with $A \cap B'$; this operation preserves $|A|+|B|$, but it cannot increase $|A\oplus B|$, since obviously any element of $A \cup B' \oplus A \cap B'$ is an element of $A \oplus B'$. Therefore, to prove the result for some $A,B$, it's enough to apply the algorithm to $A,B$ and prove the result for the two sets $A,B$ the algorithm terminates with. Note that, due to the way $c$ is chosen, $|A|$ increases monotonically throughout this algorithm, but $|A|$ is bounded by the fixed value $|A|+|B|$, hence the algorithm must terminate eventually. The only way the algorithm terminates is when there does not exist a nonnegative integer $c$ such that if $B' = B\oplus \{c\}$, then $|B| > |A \cap B'| > 0$. This is equivalent to saying that for each integer $c$, either $A$ contains $B'$ or $A$ is disjoint with $B'$. First WLOG $0\in B$; we can achieve this by choosing some $b\in B$ and replacing $B$ with $B\oplus \{ b\}$. Now interpret the integers as a vector space $\mathbb F_2^m$ for some sufficiently large $m$ so that addition is analogous to $\oplus$; then through any spanning-set-finding algorithm, we can find some elements $x_1,x_2,...,x_k$ of $B$ such that $B\subseteq \text{span} (x_1,x_2,...,x_k)$ with the $x_i$ linearly independent- that is to say, $\epsilon_1 x_1 \oplus \epsilon_2 x_2\oplus ... \oplus \epsilon_k x_k = 0$ if and only if $\epsilon_i = 0$ for each $i$. It's clear that $2^k \ge |B|$ and that $x_i\neq 0$ for each $i$. Now choose any $a\in A$; then for $c=a$, clearly $|A\cap B'|>0$, hence it follows that $B' \subseteq A$. But we know that $B'$ contains $x_i \oplus c = x_i \oplus a$ hence $A$ must too; this tells us $A$ is closed under the operation $\oplus x_i$ for each $1\le i\le k$. Therefore, we can partition $A$ into equivalence classes $A_1,A_2,...,A_m$- put $u,v\in A$ in the same class if and only if there exist $\epsilon_i \in \{0,1\}$ such that $u\oplus \epsilon_1 x_1 \oplus ... \oplus \epsilon_k x_k = v$. Each such class is "complete" in that it contains all $2^k$ possible members due to $A$ being closed under $\oplus x_i$, hence $2^km=|A|$. Note how this implies $k\le n$. Now it follows easily that $A_i \oplus B = A_i$ for each $i$, hence $|A\oplus B| = |A|=2^km$. But we know that $2^km<|A|+|B| \le 2^km + 2^k$, hence $|A\oplus B|$ is equal to the largest multiple of $2^k$ less than $|A|+|B|$ for some $k\le n$. When $2^n<|A|+|B|$, this multiple is at least $2^n$ as $2^k|2^n$, hence $|A\oplus B| \ge 2^n$ as desired.

Let $N$ be the total number of objects appearing in all the sets. Then the problem is equivalent to the following theorem. Theorem: [Restated Problem] Suppose $R,B\subseteq\mathbb{F}_2^N$ such that $|R|+|B|=2^n+1$. Then, \[|R+B|\ge |R|+|B|-1.\] This is actually a special case of the following very general (and very contrived) theorem. How the above theorem follows from this general theorem will be explained later. Theorem: [Cauchy-Davenport on Steroids] Let $K$ be a field. Now suppose $A,B\subseteq K$ such that $\binom{|A|+|B|-2}{|A|-1}\ne 0$ (in the field). Then, \[|A+B|\ge|A|+|B|-1.\] Proof: Let $C\subseteq K$ where $|C|=|A|+|B|-2$. Our goal is to show that there is some $(a,b)\in A\times B$ such that $a+b\not\in C$, or that \[f(x,y):=\prod_{c\in C}(x+y-c)\]doesn't fully vanish on $A\times B$. Note that the coefficient of $x^{|A|-1}y^{|B|-1}$ in $f$ is $\binom{|A|+|B|-2}{|A|-1}\ne 0$, so the result follows by Alon's combinatorial nullstellensatz. $\blacksquare$ Back to the original theorem. Proof: [Proof of Restated Problem] The first main claim is that $\mathbb{F}_2^N$ and $K:=\mathbb{F}_{2^N}$ are additively isomorphic. This is because $K$ is a vector space over $\mathbb{F}_2$, so it must be additiviely isomorphic to $\mathbb{F}_2^m$ for some $m$. Comparing cardinalities shows $m=N$. Therefore, the restated problem takes exactly the form of Cauchy-Davenport on steroids. All that we have to show is that \[\binom{|R|+|B|-2}{|R|-1}\not\equiv 0\pmod{2}.\]It's well known that $\binom{2^n-1}{k}$ is odd for all $0\le k\le 2^n-1$, so we're done. $\blacksquare$

Here is a solution without algebraic combinatorics: We proceed by induction on $n$, with the base case being obvious. Let $A$ be an arbitary element that shows up in $R_1\cap R_2\cap B_1\cap B_2$, if it exists. Let $R_1$ be the red sets with $A,$ $R_2$ be the red sets without $A$, $B_1$ be the blue sets with $A$ and $B_2$ without $A$ Let $\bigoplus$ denote the symmetric difference, and $R_1 \bigoplus B_1$ would denote $\{ r\bigoplus b: r\in R_1, b\in B_1\}$. Note $|R_1+B_1|+|R_2+B_2|=2^n+1$, so by pigeonhole principle, there exist at least $2^{n-1}+1$ elements in one of $R_1\bigoplus B_1$ and $R_2\bigoplus B_2$. If there are more than $2^{n-1}+1$ elements we can remove some. This gives $2^{n-1}$ distinct sets for symmetric difference without $A$ by the inductive hypothesis. Similarly, there are $2^{n-1}$ distinct sets that are symmetric difference with $A$, for a total of $2^n$ sets, as desired. If $A$ doesn't, then we employ the following process: if all the red sets of the same color have this element, then we remove this element from all the red sets. Do the same for blue sets. This doesn't affect the number of sets that are symmetric differences. After this, say $S_A=\{a_1,\cdots,a_m\}$ appear in the red sets, then they don't appear in the blue sets. Elements $S_b=\{b_1,\cdots,b_k\}$ appear in the blue sets, but they don't appear in the red sets. Since $S_A\cap S_B=\emptyset,$ the symmetric difference of any red/blue set is different, which implies that there are $|R| \cdot (2^n+1-|R|) \ge 2^n$ symmetric differences, as desired.

Remark

Let $d$ be the number of distinct elements. The stabilizer $H$ of $A+B$ is a subspace of $\mathbb{F}_{2}^d$. As $|A+H|+|B+H|$ is at least $|A|+|B|=2^n+1$ and is a multiple of $|H|=2^{\text{dim } H}$, it's at least $2^n+|H|$ and we are done by Kneser's Theorem.

Let $k$ be the total number of distinct objects over all sets. Consider the sets as elements in $\mathbb{F}_2^k$ over these elements. Take $\mathbb{F}_2^k$ as $\mathbb{F}_{2^k}$ additively. Let the red and blue categories be $R$ and $B$ respectively. The symmetric difference of two sets is then the sum of two vectors. Let $C$ be a subset of $\mathbb{F}_2^k$ with size $2^{n} - 1$. Define \[ F(x, y) = \sum_{c \in C} (x + y - C). \]This has a maximal term of the form $x^{|R| - 1}y^{|B| - 1}$. Then combinatorial nullstellensatz on $x \in R, y \in B$ gives that $R + B \not\in C$ as desired.