Maths Olympiad Prep

Library / /270 of 426

Algebra Difficulty 6.0 National Olympiad Prove it Saudi Arabia

Let FF be the set of all sequences (a1,a2,,a2020)(a_1, a_2, \dots, a_{2020}) with ai{1,1}a_i \in \{-1, 1\} for all i=1,2,,2020i = 1, 2, \dots, 2020. Prove that there exists a set SS, such that SFS \subset F, S=2020|S| = 2020 and for any (a1,a2,,a2020)F(a_1, a_2, \dots, a_{2020}) \in F there exists (b1,b2,,b2020)S(b_1, b_2, \dots, b_{2020}) \in S, such that i=12020aibi=0\sum_{i=1}^{2020} a_i b_i = 0.

Solution

For each i{1,2,,2021}i \in \{1, 2, \dots, 2021\}, let ei=(1,,1i1,1,,12021i)e_i = (\underbrace{1, \dots, 1}_{i-1}, \underbrace{-1, \dots, -1}_{2021-i}).
For two sequences a=(a1,a2,,a2020)a = (a_1, a_2, \dots, a_{2020}), b=(b1,b2,,b2020)b = (b_1, b_2, \dots, b_{2020}), we define
ab=a1b1+a2b2++a2020b2020. a \cdot b = a_1 b_1 + a_2 b_2 + \dots + a_{2020} b_{2020}.
It's easy to verify that aba \cdot b is even for each a,bFa, b \in F. Let a=(a1,a2,,a2020)Fa = (a_1, a_2, \dots, a_{2020}) \in F and denote bi=aeib_i = a \cdot e_i for each i{1,2,,2020}i \in \{1, 2, \dots, 2020\}, then
bi+1bi=aei+1aei=2aibi+1bi=2,i{1,2,,2020}. b_{i+1} - b_i = a \cdot e_{i+1} - a \cdot e_i = 2a_i \Rightarrow |b_{i+1} - b_i| = 2, \forall i \in \{1, 2, \dots, 2020\}.
Let S={e1,e2,,e2020}S = \{e_1, e_2, \dots, e_{2020}\}. It is clear that b2021=b1b_{2021} = -b_1 and bib_i is even for each i{1,2,,2020}i \in \{1, 2, \dots, 2020\}. If b10b_1 \neq 0, there exists an integer kk such that 1<k<20211 < k < 2021 and bk=0b_k = 0. Hence, SS satisfies the problem's requirements. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.