Maths Olympiad Prep

Library / /369 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

A ±1\pm 1-sequence is a sequence of 2022 numbers a1,,a2022a_{1}, \ldots, a_{2022}, each equal to either +1 or -1. Determine the largest CC so that, for any ±1\pm 1-sequence, there exists an integer kk and indices 1t1<<tk20221 \leqslant t_{1}<\ldots<t_{k} \leqslant 2022 so that ti+1ti2t_{i+1}-t_{i} \leqslant 2 for all ii, and
i=1katiC \left|\sum_{i=1}^{k} a_{t_{i}}\right| \geqslant C
(Czech Republic) Answer: The answer is C=506C=506.

A number or a short expression. Spacing and $ signs are ignored.

Solution

First, we prove that this can always be achieved. Without loss of generality, suppose at least 20222=1011\frac{2022}{2}=1011 terms of the ±1\pm 1-sequence are +1. Define a subsequence as follows: starting at t=0t=0, if at=+1a_{t}=+1 we always include ata_{t} in the subsequence. Otherwise, we skip ata_{t} if we can (i.e., if we included at1a_{t-1} in the subsequence), otherwise we include it out of necessity, and go to the next tt. Clearly, this subsequence will include all +1s. Also, for each -1 included in the sequence, a -1 must have been skipped, so at most 10112=505\left\lfloor\frac{1011}{2}\right\rfloor=505 can be included. Hence the sum is at least 1011505=5061011-505=506, as desired. Next, we prove that, for the ±1\pm 1-sequence
({1},{+1,+1},{1,1},{+1,+1},,{+1,+1},{1,1},{+1}) (\{-1\},\{+1,+1\},\{-1,-1\},\{+1,+1\}, \ldots,\{+1,+1\},\{-1,-1\},\{+1\})
each admissible subsequence atia_{t_{i}} has 506iati506-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 +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 kk 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 2k(k1)=k+12 k-(k-1)=k+1. For k<506k<506, this is at most 506. If k=506k=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 kk, not k+1k+1, so in this case the sum is also at most 506. Hence we have shown that for any admissible subsequence, iati506\sum_{i} a_{t_{i}} \leqslant 506. Analogously we can show that 506iati-506 \leqslant \sum_{i} a_{t_{i}}, meaning that C506C \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 CC so that no matter how the buckets are coloured, Sally can achieve a score of at least CC.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.