Let $n$ be an even positive integer. $F$ is the set of all sequences $\{(a_1, a_2, . . . , a_{n})\}$ with $a_i \in \{-1, 1\}$ for all $i = 1,2,...,n$. Prove that there exists a set $S$, such that $S \subset F$, $|S| = n$ and for any $(a_1,a_2,...,a_{n}) \in F$ there exists $(b_1,b_2,...,b_{n}) \in S$, such that $\sum_{i=1}^{n} a_ib_i = 0$.

$S = \{(1, 1, . . ., 1), (1, 1, . . ., 1, -1), (1, 1, . . ., 1, -1, -1), . . ., (1, -1, -1, . . ., -1)\}$ always works, where $S_j$ is a sequence of $n - j + 1$ positive ones and $j - 1$ negative ones.

In order to satisfy the condition $\sum_{i=1}^{n} a_ib_i = 0$, there must be an equal amount of $1$s and $-1$s, since $a_ib_i = \pm 1$. Therefore there exist exactly $\frac{n}{2}$ values of $1 \le i \le n$ that satisfy $a_i = b_i$, and exactly $\frac{n}{2}$ values of $1 \le i \le n$ that satisfy $a_i = -b_i$. Therefore, for any $(a_1,a_2,...,a_{n})$, the sequence $(b_1,b_2,...,b_{n})$ satisfies the condition iff there exists a way to get from $(a_1,a_2,...,a_{n})$ to $(b_1,b_2,...,b_{n})$ by swapping exactly $\frac{n}{2}$ values in $(a_1,a_2,...,a_{n})$. This means that we must prove that for any $(a_1,a_2,...,a_{n}) \in F$ there exists $(b_1,b_2,...,b_{n}) \in S$ such that we can go from $(a_1,a_2,...,a_{n})$ to $(b_1,b_2,...,b_{n})$ by swapping exactly $\frac{n}{2}$ values.

Consider splitting $(a_1,a_2,...,a_{n})$ into two parts, which are $X = (a_1, a_2, ..., a_k)$ and $Y = (a_{k + 1}, a_{k + 2}, ..., a_{n})$. Let the amount of $-1$s in $X$ be $p$, and the amount of $1$s in $Y$ be $q$. If there exists a $k$ with $0 \le k \le n$ that satisfies $p + q = \frac{n}{2}$, then we can use exactly $\frac{n}{2}$ swaps to turn $X$ into all positive ones, and $Y$ into all negative ones. This will form one of the sequences in $S$ ($(-1, -1, ..., -1)$ works iff $(1, 1, ..., 1)$ works), thus finishing the problem. Let $c$ be the amount of positive ones in $(a_1, a_2, ..., a_n)$, and let $d$ be the amount of negative ones. If $c = d$ then we have $\sum_{i=1}^{n} a_i = 0$ so $(b_1,b_2,...,b_{n}) = (1, 1, ..., 1)$ works. So we suppose $c \neq d$. When $k = 0$ we have $p + q = 0 + c = c$, and when $k = n$ we have $p + q = d + 0 = d$. We notice that when we go from $k$ to $k + 1$, the sum $p + q$ either increases or decreases by $1$. This is because we are either removing a $1$ from $Y$, or adding a $-1$ to $X$. If $c > d$, then we have $c > \frac{n}{2} > d$. So when we go from $k = 0 \to n$ the sum $p + q$ is going from being greater than $\frac{n}{2}$ to less than $\frac{n}{2}$. But this means that at some point, $p + q = \frac{n}{2}$ must have happened, so we are done. If $c < d$, then we have $c < \frac{n}{2} < d$. So when we go from $k = 0 \to n$ the sum $p + q$ is going from being less than $\frac{n}{2}$ to greater than $\frac{n}{2}$. But this means that at some point, $p + q = \frac{n}{2}$ must have happened, so we are done. Since all cases have been taken, we have proved the general statement.