Let F is the set of all sequences {(a1,a2,...,a2020)} with ai∈{−1,1} for all i=1,2,...,2020. Prove that there exists a set S, such that S⊂F, |S|=2020 and for any (a1,a2,...,a2020)∈F there exists (b1,b2,...,b2020)∈S, such that ∑2020i=1aibi=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 {(a1,a2,...,an)} with ai∈{−1,1} for all i=1,2,...,n. Prove that there exists a set S, such that S⊂F, |S|=n and for any (a1,a2,...,an)∈F there exists (b1,b2,...,bn)∈S, such that ∑ni=1aibi=0.
S={(1,1,...,1),(1,1,...,1,−1),(1,1,...,1,−1,−1),...,(1,−1,−1,...,−1)} always works, where Sj is a sequence of n−j+1 positive ones and j−1 negative ones.
In order to satisfy the condition ∑ni=1aibi=0, there must be an equal amount of 1s and −1s, since aibi=±1. Therefore there exist exactly n2 values of 1≤i≤n that satisfy ai=bi, and exactly n2 values of 1≤i≤n that satisfy ai=−bi.
Therefore, for any (a1,a2,...,an), the sequence (b1,b2,...,bn) satisfies the condition iff there exists a way to get from (a1,a2,...,an) to (b1,b2,...,bn) by swapping exactly n2 values in (a1,a2,...,an).
This means that we must prove that for any (a1,a2,...,an)∈F there exists (b1,b2,...,bn)∈S such that we can go from (a1,a2,...,an) to (b1,b2,...,bn) by swapping exactly n2 values.
Consider splitting (a1,a2,...,an) into two parts, which are X=(a1,a2,...,ak) and Y=(ak+1,ak+2,...,an). Let the amount of −1s in X be p, and the amount of 1s in Y be q. If there exists a k with 0≤k≤n that satisfies p+q=n2, then we can use exactly n2 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 (a1,a2,...,an), and let d be the amount of negative ones.
If c=d then we have ∑ni=1ai=0 so (b1,b2,...,bn)=(1,1,...,1) works. So we suppose c≠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>n2>d. So when we go from k=0→n the sum p+q is going from being greater than n2 to less than n2. But this means that at some point, p+q=n2 must have happened, so we are done.
If c<d, then we have c<n2<d. So when we go from k=0→n the sum p+q is going from being less than n2 to greater than n2. But this means that at some point, p+q=n2 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,⋯,−1) as well (but don't actually add it in S, since (1,1,⋯,1) works iff (−1,−1,⋯,−1) works so we can safely remove it). Then, if we let X(bi)=∑aibi, then X(−1,−1,⋯,−1) and X(1,1,⋯,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 ±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.