This set minimize the minimum?

Question

Let $S$ a finite set and let $A \subseteq S$ and $B \subseteq S$.

We can say that $Z = B$ minimize the following minimum: $$\min_{Z \subseteq S} \{|A \cap Z| + |B-Z|\}$$? If yes, why?

Answer 1

First, show one direction: $|A\cap B| \ge \min_Z \{|A\cap Z|+|B-Z|\},$ because you can always try $Z=B$. Now to show $|A\cap B| \le |A\cap Z|+|B-Z|$ for any $Z$. You can always add to any given $Z$, all the elements $z\in (B-Z)-A$ and only decrease the right-hand side (you'll be making the 2nd term smaller). Then add anything $z\in (A\cap B) - Z$ which will not change the right-hand side. Remove any $z$ outside of $A$ and $B$. You end up with $Z=B$.

Answer 2

For $i\in S$, let binary decision variable $z_i$ indicate whether $i\in Z$. The problem is to minimize \begin{align} \sum_{i\in S} \left([i\in A] z_i + [i\in B] (1-z_i) \right) &= \sum_{i\in A} z_i + \sum_{i\in B} (1-z_i) \\ &= \left(\sum_{i\in A \setminus B} z_i + \sum_{i\in A \cap B} z_i\right) + \left(|B| - \sum_{i\in A \cap B} z_i - \sum_{i\in B \setminus A} z_i\right) \\ &= \sum_{i\in A \setminus B} z_i + |B| - \sum_{i\in B \setminus A} z_i \end{align} Now it is clear that every optimal solution must satisfy: $$z_i=\begin{cases}0 &\text{if $i\in A \setminus B$}\\1 &\text{if $i\in B \setminus A$}\end{cases}$$ For all other $i \in S$, you can set $z_i$ arbitrarily. In particular, $Z = B$ is one of the optimal solutions.