MathDB

9.7

Part of 2000 Saint Petersburg Mathematical Olympiad

Problems(1)

Sequences and parity

Source: St. Petersburg MO 2000, 9th grade, P7

4/22/2023
Define a complexity of a set a1,a2,…,a_1,a_2,\dots, consisting of 0 and 1 to be the smallest positive integer kk such that for some positive integers ϵ1,ϵ2,…,ϵk\epsilon_1,\epsilon_2,\dots, \epsilon_k each number of the sequence ana_n, n>kn>k, has the same parity as ϵ1an−1+ϵ2an−2+⋯+ϵkan−k\epsilon_1 a_{n-1}+\epsilon_2 a_{n-2}+\dots+\epsilon_k a_{n-k}. Sequence a1,a2,…,a_1,a_2,\dots, has a complexity of 10001000. What is the complexity of sequence 1−a1,1−a2,…,1-a_1,1-a_2,\dots,.
[I]Proposed by A. Kirichenko
algebraSequenceParity