Let $F$ is the set of all sequences $\{(a_1, a_2, . . . , a_{2020})\}$ with $a_i \in \{-1, 1\}$ for all $i = 1,2,...,2020$. Prove that there exists a set $S$, such that $S \subset F$, $|S| = 2020$ and for any $(a_1,a_2,...,a_{2020}) \in F$ there exists $(b_1,b_2,...,b_{2020}) \in S$, such that $\sum_{i=1}^{2020} a_ib_i = 0$.
Problem
Source: 2021 Saudi Arabia JBMO TST 1.4
Tags: combinatorics
expsaggaf
16.12.2024 12:44
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.
vsamc
16.12.2024 15:23
Another way to see that the claim is true is to include $(-1, -1, \cdots, -1)$ as well (but don't actually add it in $S$, since $(1,1,\cdots, 1)$ works iff $(-1, -1, \cdots, -1)$ works so we can safely remove it). Then, if we let $X(b_i) = \sum a_ib_i$, then $X(-1,-1,\cdots, -1)$ and $X(1,1,\cdots, 1)$ have different signs (or they are both zero, in which case we are done). Then, note that $X$ is always even, and it changes by $\pm 2$ every time you go one element to the right in $S$. So by discrete IVT, since it switches signs, it follows that at one point $X$ will be $0$, i.e. $S$ works.