Let F be 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 ∑i=12020aibi=0.
Solution
For each i∈{1,2,…,2021}, let ei=(i−11,…,1,2021−i−1,…,−1). For two sequences a=(a1,a2,…,a2020), b=(b1,b2,…,b2020), we define a⋅b=a1b1+a2b2+⋯+a2020b2020. It's easy to verify that a⋅b is even for each a,b∈F. Let a=(a1,a2,…,a2020)∈F and denote bi=a⋅ei for each i∈{1,2,…,2020}, then bi+1−bi=a⋅ei+1−a⋅ei=2ai⇒∣bi+1−bi∣=2,∀i∈{1,2,…,2020}. Let S={e1,e2,…,e2020}. It is clear that b2021=−b1 and bi is even for each i∈{1,2,…,2020}. If b1=0, there exists an integer k such that 1<k<2021 and bk=0. Hence, S satisfies the problem's requirements. □
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.