Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /250 of 395

Saudi Arabian Mathematical Competitions

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 S⊂FS \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,…,1⏟i−1,−1,…,−1⏟2021−i)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
a⋅b=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 a⋅ba \cdot b is even for each a,b∈Fa, b \in F. Let a=(a1,a2,…,a2020)∈Fa = (a_1, a_2, \dots, a_{2020}) \in F and denote bi=a⋅eib_i = a \cdot e_i for each i∈{1,2,…,2020}i \in \{1, 2, \dots, 2020\}, then
bi+1−bi=a⋅ei+1−a⋅ei=2ai⇒∣bi+1−bi∣=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 b1≠0b_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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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