Any Ideas ?

I have a construction to make the sum $n+1$. For $S=\{1,2,\ldots,2n\} \text{ or } \{1,2,\ldots ,2n-1\}$, choose $A=B=\{1,2,\ldots ,n\}$. For small size of $S$, i cant seem to find a better bound than it. So I guess that is the answer? No idea how to prove it though.

Let $X=A\cap S$ so $S=X \cup A'$ with $A' \cap X = \emptyset$. Similarly let $Y=B\cap S$ and $B = Y \cup B'$. 1) Now, $|A\Delta S| = |A\cup S|-|A\cap S| = |A'| + |S| - |X|$. And similarly $|B \Delta S| = |B'| + |S| - |Y|$ 2) Let $A$ have elements $a_1 < a_2 < ... < a_m$ and $B$ have elements $b_1 < ... < b_k$. Then the sums $a_1+b_j$, for $j=1,2,...,k$ then $a_i + b_k$ for $i=1,2,...,m$ for a strictly increasing sequence with $m+k-1 = |A| + |B| -1$ terms. Hence $|A+B| \ge |A| + |B| - 1$ Case 1: $A,B \subseteq S$ If $A,B \subseteq S$ then $1 \not \in (A+B)$ because $\min\{A\}, \min\{B\} \ge 1$. So $|(A+B) \cap S| \le n-1$ and $| (A+B)\cup S|\ge (|A|+|B|-1)+1$, so $|(A+B)\Delta S| \ge |A|+|B| - (n-1)=|X|+|Y|-(n-1)$ (Since $|A'|=|B'|=0$) Putting it all together $ |A\Delta S|+|B\Delta S|+|C\Delta S| \ge 2n - |X| - |Y|+|X|+|Y|-n+1 = n+1 $ Case 2: At least one of $A,B \not \subseteq S$ In this case $|(A+B)\Delta S| \ge |A| + |B| - 1 - |S| = |A'|+|X|+|B'|+|Y|-n-1$ Putting everything together gives $ |A\Delta S|+|B\Delta S|+|C\Delta S| \ge n-1 + 2|A'| + 2|B'| \ge n+1$, because we have assume $|A'|$ or $|B'| \ge 1$ (else they would be subsets of $S$). Equality occurs when $A=B=S$ This completes the proof.

ocha wrote: ... Now clearly $1 \not \in (A+B)$ because .... The answer is true but your proof has a small mistake , $A,B$ can be any set so this sitution can happen that $1$ belongs to $A+B$ .

mahanmath wrote: ocha wrote: ... Now clearly $1 \not \in (A+B)$ because .... The answer is true but your proof has a small mistake , $A,B$ can be any set so this sitution can happen that $1$ belongs to $A+B$ . How $1$ can be written as the sum of the two natural numbers?

ehsan2004 wrote: mahanmath wrote: ocha wrote: ... Now clearly $1 \not \in (A+B)$ because .... The answer is true but your proof has a small mistake , $A,B$ can be any set so this sitution can happen that $1$ belongs to $A+B$ . How $1$ can be written as the sum of the two natural numbers? $A,B$ are not necessary subsets of $\mathbb N$ zhaobin wrote: For any nonempty set $A$ and $B$

mahanmath wrote: The answer is true but your proof has a small mistake , $A,B$ can be any set so this sitution can happen that $1$ belongs to $A+B$ . Ah you're right, that was silly of me. I've edited the solution.

Just came across an easy solution today: First, taking $A=B=S$ gives $\ell := |A\Delta S|+|B\Delta S|+|C\Delta S| = n+1$. We'll show that this is the desired minimum. We have $\ell = \underbrace{ |A\setminus S| + |B\setminus S| +|S\setminus C|}_{\ell_1} +\underbrace{ |S\setminus A| + |S\setminus B| +|C\setminus S|}_{\ell_2}$. If $\ell_1=0$, we get that $A,B\subseteq S\implies 1\not\in C$ and $S\subseteq C\implies 1\in C$. Contradiction. Hence, $\ell_1\geqslant 1$. If $A\cap S =\emptyset$ we'll get $\ell_2 \geqslant |S\setminus A|=n$. Otherwise let $k$ denote the maximum element of $A\cap S$. We get that $|S\setminus A|\geqslant n-k$. Moreover, for each $n-k+1\leqslant i\leqslant n$ either $i\in B\implies i+k\in C\setminus S$ or $i\not\in B\implies i\in S\setminus B$. Hence, we get $\ell_2 \geqslant (n-k)+k=n$. Finally, we get $\ell =\ell_1+\ell_2\geqslant n+1$.