Maths Olympiad Prep

Library / /135 of 144

Combinatorics Difficulty 8.9 Shortlist Find the answer

A ±1\pm 1-*sequence* is a sequence of 20222022 numbers a1,,a2022,a_1, \ldots, a_{2022}, each equal to either +1+1 or 1-1. Determine the largest CC so that, for any ±1\pm 1-sequence, there exists an integer kk and indices 1t1<<tk20221 \le t_1 < \ldots < t_k \le 2022 so that ti+1ti2t_{i+1} - t_i \le 2 for all ii, and i=1katiC.\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To solve the given problem, we first need to understand the requirements for a ±1\pm 1-sequence. We are looking for the largest integer C C such that, for any sequence of numbers a1,a2,,a2022 a_1, a_2, \ldots, a_{2022} where each ai a_i is either +1 +1 or 1 -1 , there exists a subsequence satisfying certain conditions.

### Problem Breakdown:

- We need to identify a subsequence at1,at2,,atk a_{t_1}, a_{t_2}, \ldots, a_{t_k} with:
- Indices t1,t2,,tk t_1, t_2, \ldots, t_k such that 1t1<t2<<tk2022 1 \le t_1 < t_2 < \ldots < t_k \le 2022 .
- The difference between consecutive indices is ti+1ti2 t_{i+1} - t_i \le 2 .
- The absolute value of the sum of the subsequence elements satisfies i=1katiC\left|\sum_{i=1}^k a_{t_i}\right| \ge C.

### Solution Approach:

The essence of the problem is to ensure that there always exists a subsequence where the sum is as large as possible given the constraints on indices.

Key Idea:
- If we take any two consecutive elements in the sequence, denoted as ai a_i and ai+1 a_{i+1} , the sum ai+ai+1 a_i + a_{i+1} can be 0 0 (if ai=ai+1 a_i = -a_{i+1} ), +2 +2 (if both are +1 +1 ), or 2 -2 (if both are 1 -1 ).
- Hence, checking groups of 3 consecutive elements, ai,ai+1, a_i, a_{i+1}, and ai+2 a_{i+2} , we can form subsequences with sums of absolute value 1, 2, or 3.
- The strategy is to maximize the deviation by optimally grouping these sequences.

Construction:
1. Analyze small groups of consecutive terms such as (ai,ai+1,ai+2) (a_{i}, a_{i+1}, a_{i+2}) , and decide whether to take two or more elements to maximize the absolute sum.
2. Since 2022=673×3+1 2022 = 673 \times 3 + 1 , there are effectively 673 673 full groups of 3 elements we can evaluate, plus one extra element.
3. For each group of three elements (ai,ai+1,ai+2) (a_{i}, a_{i+1}, a_{i+2}) , the maximum absolute sum we can always achieve is 1, capturing the nature of any sequence distribution.

Conclusion:
By consistently leveraging groups of up to three elements, thereby utilizing every potential subsequence opportunity with =±1 \sum = \pm 1 , the minimum C=506 C = 506 can be achieved across 673 673 groups:
- For each of the 673 groups of three consecutive numbers, we can guarantee a sum of magnitude 1, resulting in 506 506 as the worst-case minimum.

Thus, the largest C C we can guarantee for any ±1\pm 1-sequence under the given conditions is:
506. \boxed{506}.

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