A -sequence is a sequence of 2022 numbers , each equal to either +1 or -1. Determine the largest so that, for any -sequence, there exists an integer and indices so that for all , and
(Czech Republic) Answer: The answer is .
Solution
First, we prove that this can always be achieved. Without loss of generality, suppose at least terms of the -sequence are +1. Define a subsequence as follows: starting at , if we always include in the subsequence. Otherwise, we skip if we can (i.e., if we included in the subsequence), otherwise we include it out of necessity, and go to the next . Clearly, this subsequence will include all +1s. Also, for each -1 included in the sequence, a -1 must have been skipped, so at most can be included. Hence the sum is at least , as desired. Next, we prove that, for the -sequence
each admissible subsequence has . We say that the terms inside each curly bracket is a block. In total, there are 1012 blocks - 506 of them hold +1s, and 506 of them hold -1s. (The two blocks at each end hold 1 number each, each other block holds 2.) Suppose an admissible subsequence includes terms from blocks holding +1s. 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 +1s included from each +1-block, and at least one -1 must be included from each -1-block, so the sum is at most . For , this is at most 506. If , 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 , not , so in this case the sum is also at most 506. Hence we have shown that for any admissible subsequence, . Analogously we can show that , meaning that 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 so that no matter how the buckets are coloured, Sally can achieve a score of at least .