A \(\pm 1\)-sequence is a sequence of \(2022\) numbers \(a_1, \ldots, a_{2022},\) each equal to either \(+1\) or \(-1\). Determine the largest \(C\) so that, for any \(\pm 1\)-sequence, there exists an integer \(k\) and indices \(1 \le t_1 < \ldots < t_k \le 2022\) so that \(t_{i+1} - t_i \le 2\) for all \(i\), and
\[\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.\]
Answer: The answer is \(C=506\).
First, we prove that this can always be achieved. Without loss of generality, suppose at least \(\frac{2022}{2}=1011\) terms of the \(\pm 1\)-sequence are \(+1\). Define a subsequence as follows: starting at \(t=0\), if \(a_{t}=+1\) we always include \(a_{t}\) in the subsequence. Otherwise, we skip \(a_{t}\) if we can (i.e. if we included \(a_{t-1}\) in the subsequence), otherwise we include it out of necessity, and go to the next \(t\). Clearly, this subsequence will include all \(+1\)s. Also, for each \(-1\) included in the sequence, a \(-1\) must have been skipped, so at most \(\left\lfloor\frac{1011}{2}\right\rfloor=505\) can be included. Hence the sum is at least \(1011-505=506\), as desired.
Next, we prove that, for the \(\pm 1\)-sequence
\[(\{-1\},\{+1,+1\},\{-1,-1\},\{+1,+1\}, \ldots,\{+1,+1\},\{-1,-1\},\{+1\})\]
each admissible subsequence \(a_{t_{i}}\) has \(-506 \leqslant \sum_{i} a_{t_{i}} \leqslant 506\). We say that the terms inside each curly bracket is a block. In total, there are \(1012\) blocks - \(506\) of them hold \(+1\)s, and \(506 of them hold \)-1\(s. (The two blocks at each end hold \)1\( number each, each other block holds \)2\(.)Suppose an admissible subsequence includes terms from \)
k\( blocks holding \)+1\(s. Then, in each \)-1\(-pair in between the \)+1\(-pairs, the subsequence must also include at least one \)-1\(. There can be at most two \)+1\(s included from each \)+1\(-block, and at least one \)-1\( must be included from each \)-1\(-block, so the sum is at most \)2k-(k-1)=k+1\(.For \)
k<506\(, this is at most \)506\(. If \)k=506\(, one of the \)+1\(-blocks must be the one at the end, meaning it can only include one \)+1\(, so that the maximum in this case is only \)k\(, not \)k+1\(, so in this case the sum is also at most \)506\(.Hence we have shown that for any admissible subsequence, \)
\sum_{i} a_{t_{i}} \leqslant 506\(. Analogously we can show that \)-506 \leqslant \sum_{i} a_{t_{i}}\(, meaning that \)C \leqslant 506\( as desired.Comment. A possible reformulation of the problem is the following:
2022 buckets of water are arranged in a row, each coloured either red or blue.
Sally the salmon plays a game in the following way: first, she chooses any
bucket she likes to start in. Then, any number of times she may jump either
to the next bucket in the row, or across it to land in the bucket after that.
(She may not jump across more than one bucket.) At any point, she may finish
the game. At that time, her score is the absolute value of the difference
between the number of red and blue buckets she visited during the game.
Determine the largest \)