IMO Shortlist 2022 C1

 

Today we shall try IMO Shortlist $2022$ C1.

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.$$

We claim that the answer is $\boxed{506}$.

$506$ is the upper bound.

Just consider the sequence $$+1,-1,-1,+1,+1,-1,-1,+1\dots,-1,-1,+1,+1,-1.$$ Here $1, -1, -1, 1$ is repeated $505$ times and $1,-1$ is concatted to it. Now,our sequence would be $a_1,a_3,a_4,a_5,a_7,\dots$ which on summing would give $506$. And clearly, this would give the upper bound.

Now, we show that $506$ is attainable by every sequence. WLOG there are at least $1011$ positive numbers in the sequence. Then we choose $+1$ whenever we can. Let the sequence be $c_1,b_1,\dots, c_n,b_n$ where $c_i$ are the sequence of $+1$s and $b_i$ are the sequences of $-1$. Then the maximal number we can get is $$\sum |c_i|+\sum |b_i|/2\ge1011+(-1011)/2=1011/2>505.$$

I think the contruction itself is easy but well, explaining it is pretty non-trivial! I liked proving the attainablity condition! Very cute problem!

Yep! Hope you liked the problem! Will be back with another combo tomorrow! ~Sunaina(13/01/2024)