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.$$
Problem
Source: ISL 2022/C1
Tags: combinatorics, Integer sequence, ISL 2022
Tintarn
09.07.2023 08:35
$506$
First consider the sequence $1,-1,-1,1,1,-1,-1,1,1,\dots,-1,-1,1,1,-1$. Suppose that $C \ge 507$. By symmetry, we may suppose that we have found a positive subsum $\ge 507$, and w.l.o.g. the first and last term are positive. If there are $m$ of the $505$ blocks with entries $-1$ in between, we have to choose at least $m$ times $-1$ and at most $2m+2$ entries $+1$, so that the sum is at most $m+2 \le 507$.
But to reach equality, we need $m=505$, but then we can choose at most $2m+1=1011$ entries $+1$ (there are no more). Contradiction! Hence indeed $C \le 506$.
On the other hand, let us prove that we can always find a subsum of absolute value at least $506$.
W.l.o.g. there are at least $1011$ positive numbers in the initial sequence. We then choose all entries $+1$ and at most every second entry $-1$. This way we choose at least $1011$ entries $+1$ and at most $505$ entries $-1$, resulting in a sum of at least $506$ as desired.
Remark: If we replace $2022$ by $n$, the same argument shows that the answer is $C=\left\lceil \frac{n+2}{4}\right\rceil$.
CrazyInMath
09.07.2023 08:47
The solution might be flawed but I would post it here
First, we notice that if we go like $RB,RBBR,RBBR,...,RBBR$ then one of the two adjacent $B$ must be landed on, therefore at least half a kind must be landed on, so with $1011$ blue buckets, you have to visit at least $505$ of them, so the max would be $506$ as you can visit all the red ones.
Now we call a sequence of some adjacent bucket of the same color a "string". It is clear that you can visit as few as $\lfloor \frac{n}{2}\rfloor$ buckets in a string of length $n$ (by alternating visit and not visit, and not visiting the first one in a string), so we found that there is a way you can visit no more than half of the buckets of a color (if you always visit the last one of the last string). Let there be $R$ red buckets and $B$ blue buckets and WLOG let $R\geq B$, we can get a score of $R-\lfloor \frac{B}{2}\rfloor$, which is at least $506$.
edit: I wrote the solution with the statement @below
ike.chen
09.07.2023 08:50
For context, this problem appeared during the US IMO Training Camp with the following flavor text: MOP Test 4 wrote: There are $2022$ buckets of water arranged in a row, each colored red or blue. Sally the salmon plays the following game: 1. First, she chooses any bucket to start in and begins to jump. 2. At each step, she may jump to the next bucket, or the one after that. 3. She may stop jumping at any point, ending the game. After the game ends, her score is the absolute value of the difference between the number of red buckets and the number of blue buckets she visited. Find the largest possible score Sally can achieve, regardless of the colors of the buckets.
VicKmath7
09.07.2023 10:34
We claim that the answer is $C=506$.
Consider a random $\pm 1$-sequence and suppose that WLOG it contains at least $n \geq 1011$ ones. We will choose the $t_i$ as follows: divide the sequence into blocks of $1$'s and $-1$'s and take all blocks of $1$ and every second $-1$, taking at most $\frac{1}{2}$ of the $-1$ from every such block. Then the sum will be at least $n-\frac{2022-n}{2}=\frac{3n-2022}{2} \geq 506$, so $C=506$ always works.
To prove that $C=507$ doesn't work, we will take the sequence $-1, 1, 1, -1, -1, 1, 1, \ldots, -1, -1, 1$, which has equal number of $1$ and $-1$ and we have $506$ blocks of $1$ - $505$ with length $2$ and $1$ unit block. Suppose that we have taken $1$'s from $k$ blocks; we will prove that the sum is smaller than $506$, because similarly we can obtain that the sum is greater than $-506$.
$\textbf{Case 1.}$ $k \leq 505$. Notice that we have taken at least one $-1$ from each $-1$-block between two blocks of ones, so the sum is at most $2k-(k-1)=k+1 \leq 506$.
$\textbf{Case 2.}$ $k=506$. Then in a similar manner, we obtain that the sum is at most $2k-1-(k-1)=506$ (since we have an unit block).
cj13609517288
09.07.2023 23:53
The answer is $\boxed{506}$, achieved by $+--++--+...+--++-$. If you really want a proof for why this gives $506$ use dp or something. To prove that $506$ is the lowest you can get, consider the following algorithm: Start at the first $+$, then go through every $+$ and go through every other $-$ in a gap(so say if we have $++---+++$ we go through indices $1,2,4,6,7,8$). The algorithm where you swap $+$ and $-$ is the other algorithm we will consider. In both cases, we go through at most half of each gap, so we can just consider what happens if we go through half of the other sign. Let $x$ be the number of $+$s, so there are $2022-x$ $-$s. Then we must have \[C\le \text{max}\left(x-\frac{2022-x}{2},2022-x-\frac{x}{2}\right) = \text{max}\left(\frac{3x-2022}{2},\frac{4044-3x}{2}\right).\]This is the maximum of two numbers that sum up to $1011$, so it must be at least $505.5$, so it must be at least $506$. $\blacksquare$
megarnie
11.07.2023 00:36
Solved with OronSH. The answer is $\boxed{506}$. The construction is $1, -1, -1, 1, 1, -1, -1, 1, \ldots, 1, -1, -1, 1, 1, -1$, where $1, -1, -1, 1$ is repeated $505$ times and $1, -1$ is added to it. Notice the maximal sum we can get in each block of $1,-1,-1,1$ is $1$, and the maximal sum we can get in $1,-1$ is $1$, so we have a maximal value of $505\cdot 1 + 1 = 506$. Similarly, the minimal sum we can get in $-1,1,1,-1$ is $-1$, and the minimal sum we can get in $1,-1$ is $-1$, so we have a minimal value of $(-1) + -1 \cdot 505 = -506$, as desired. Now we show that we can always create a subsequence as in the problem with absolute value at least $506$. WLOG that there are at least $1011$ ones. Let $A$ be the number of ones and $B$ be the number of negative ones in total. The idea is to select every single $1$, and the every second element in each string of $-1$'s. This selection satisfies $t_{i+1} - t_i \le 2$. This gives us a total of at least $A - B/2 \ge 1011 - 1011/2 = 505.5$. Since it must be an integer, it is at least $506$.
OgnjenTesic
11.07.2023 01:43
WLOG, we can assume that we have an equal or greater number of $1$ than $-1$ (since we are considering the sum in terms of absolute value). Let's consider the "blocks" of $-1$. Let's say that in the first "block" we have $n_1$ numbers $-1$, in the second "block" we have $n_2$, ..., and in the $k$-th block, we have $n_k$ numbers $-1$: $$\dots \underbrace{-1,-1,-1,\dots,-1}_{n_1}, 1,1,1, \dots, 1, \underbrace{-1,-1,-1,\dots,-1}_{n_2},1,1,1, \dots,1, \underbrace{-1,-1,-1,\dots,-1}_{n_k}, \dots$$In a block of $x$ number $-1$, we have to take at least $\left \lfloor{\frac{x}{2}}\right \rfloor$ numbers. Therefore, sum of $-1$ is at most $$\left \lfloor{\frac{n_1}{2}}\right \rfloor+\left \lfloor{\frac{n_2}{2}}\right \rfloor+\dots+\left \lfloor{\frac{n_k}{2}}\right \rfloor\leqslant \left \lfloor{\frac{n_1+n_2+\dots+n_k}{2}}\right \rfloor=\left \lfloor{\frac{1011}{2}}\right \rfloor=505\text{.}$$So for every $\pm 1$-sequence, we can achieve sum $1011-505=506$. ($1011$ because we have at least 1011 number $1$) Construction for $506$: $\underbrace{1, -1, -1, 1}{}, \underbrace{1, -1, -1, 1}{}, \dots, \underbrace{1, -1, -1, 1}, 1, -1$.
bobthegod78
14.07.2023 17:42
The answer is $506$, with equality achieved using 505 copies of $1,-1,-1,1$ and then a $1,-1$ at the end. To show this achieves it, consider each block of 4 (plus one block of 2), we can get at most one from each of these and it follows easily. Let there be at most as many $-1$s as $1$s, then take as little $-1$'s as you can to take all the $+1$s. Let $c(1),c(-1)$ denote the number of 1s and -1s respectively. For each block of $x$ negatives, we need to take at least $\left\lfloor \frac x2 \right\rfloor$ of them. Then the problem follows since \[ c(1) - \sum_{\text{block of } x} \left\lfloor \frac x2 \right\rfloor \geq 1011 - \left\lfloor \frac{1011}{2} \right\rfloor = 506, \]as desired.
vsamc
14.07.2023 20:05
The answer is $C = \boxed{506}$.
To show that $C \leq 506$, consider $$a_i = \begin{cases} 1 & i\in \{0, 1\}\pmod{4} \\ -1 & i\in \{2, 3\}\pmod{4} \end{cases}.$$We will first prove a crucial lemma.
Lemma: Consider some sequence of indices $\{t_i\}$ that satisfy the condition in the problems. Then, for any positive integer $x$ with $t_1 \leq x < x+1 \leq t_k$, at least one of $\{x, x+1\}$ is in $\{t_i\}$.
Proof: Assume the contrary. Since $t_1 \leq x$, there exists a maximal $i$ for which $t_i \leq x$. Since we assume that $x$ is not in $\{t_i\}$, we must have $t_i < x$, so $t_i \leq x-1$. Then, $t_{i+1} > t_i$, but $t_{i+1} \notin \{x, x+1\}$, so $t_{i+1} \geq x+2$. Thus, $$2\geq t_{i+1} - t_i \geq (x+2) - (x-1) = 3,$$a contradiction. $\square$
Now, take some sequences of indices $\{t_i\}$ that satisfy the conditions in the problems. Suppose that such a $t_i$ was maximal, i.e. $\left | \sum_{i=1}^{k}a_{t_i}\right |$ is maximized. Clearly $\sum_{i=1}^{k}a_{t_i} \neq 0$, since $\{t_i\} = \{1\}$ gives the absolute value of the sum to be $1 > 0$, contradiction the maximality of $\{t_i\}$. Thus, we have two cases.
Case 1: $\sum_{i=1}^{k}a_{t_i} > 0$.
Then, it is clearly optimal to have $a_{t_1}$ and $a_{t_k}$ as $+1$, since if $a_{t_1} = -1$, then getting rid of $t_1$ in the sequence of indices (i.e. making the new sequence of indices $t_2, \cdots, t_k$) will make $\left |\sum_{i=1}^{k}a_{t_i} \right | = \sum_{i=1}^{k}a_{t_i} $ increase by $1$, contradicting the maximality of $\left | \sum_{i=1}^{k}a_{t_i} \right |$ over all $\{t_i\}$, and similarly if $a_{t_k} = -1$, we can take the sequence of indices $t_1, t_2, \cdots, t_{k-1}$ which will make the absolute value of the sum bigger, contradicting the maximality of it. So we must have $a_{t_1} = a_{t_k} = 1$.
If $t_1 = 1$, then if we take the smallest index $j$ for which $t_j\geq 4$, we have that $$\sum_{i=j}^{k}a_{t_i} \geq \sum_{i=1}^{k}a_{t_i},$$since $\sum_{i=1}^{j-1}a_{t_i} \leq 0$ since $(a_1, a_2, a_3)$ is $(1, -1, -1)$ and $t_{j-1} \leq 3$ by the minimality of $j$, and one of $\{2, 3\}$ must be in $\{t_1, t_2, \cdots, t_{j-1}\}$. Thus, $\sum_{i=j}^{k}a_{t_i}$ is positive, so its absolute value is at least that of $\sum_{i=1}^{k}a_{t_i}$, so $(t_j, t_{j+1}, \cdots, t_k)$ is maximal as well, so we may assume that $t_1 > 1$, since even though there could exist a maximal $\{t_i\}$ with $t_1 = 1$, we can truncate every index less than $4$ and get a maximal $\{t_i\}$ for which the first index is at least $4$ anyways (remember, our goal here is to show that this maximal value is less than or equal to $506$, so it does not matter which sequence we take, so long as it attains that maximal value). Thus, since $t_1 > 1$ and $a_{t_1} = 1$, we must have $t_1 \geq 4$. Now, let $B_j = \{2j, 2j+1\}$ for all $2\leq j\leq 1010$. Note that $a_{2022} = -1$, so $t_k \leq 2021$, so $t_1$ and $t_k$ are in $B_j$'s. Note that $i\in B_j$ has $a_i = 1$ if $j$ is even and $a_i = -1$ if $j$ is odd. Thus, since $a_{t_1} = a_{t_k} = 1$, we have that $t_1 \in B_{2r}, t_k\in B_{2s}$ for some $1\leq r \leq s\leq 505$. Now, note that the number of $+1$'s in $\{a_{t_i}\}$ is at most $2(s-r+1)$, since the $+1$'s can only come from $B_{2r}, B_{2r+2}, \cdots, B_{2s}$, and there are $2$ in each, and $s-r+1$ of them. By the lemma, we have that for each odd $2r < j < 2s$, since $t_1 \leq 2j < 2j+1 \leq t_k$, we have that there exists a $t_i \in B_j$, so since $j$ is odd, $a_{t_i} = -1$. Now, the number of odd $2r < j < 2s$ is $\frac{(2s-1) - (2r+1)}{2} + 1 = s - r$, so there are at least $s-r$ of $-1$'s in $\{a_{t_i}\}$. Thus, we have that $$\left |\sum_{i=1}^{k}a_{t_i} \right | = \sum_{i=1}^{k}a_{t_i} \leq (2(s-r+1)) - (s-r) = s-r + 2 \leq 505 - 1 + 2 = 506,$$as desired.
Case 2: $\sum_{i=1}^{k}a_{t_i} < 0$.
Then, note that $a_n = -a_{2023-n}$ for all $1\leq n\leq 2022$, so we have that $$-\sum_{i=1}^{k}a_{2023-t_i} = \sum_{i=1}^{k}-a_{2023-t_i} = \sum_{i=1}^{k}a_{t_i} < 0,$$so $$\sum_{i=1}^{k}a_{2023-t_i} > 0.$$Now, note that $(2023-t_k, 2023-t_{k-1}, \cdots, 2023 - t_1)$ is a valid sequence since $1\leq 2023 - t_k < 2023 - t_{k-1} < \cdots < 2023 - t_1 \leq 2022$, and $(2023-t_{k-i}) - (2023 - t_{k+1-i}) = t_{k+1-i} - t_{k-i} \leq 2$ for all $1\leq i\leq k-1$, so by the previous case, we have that $$\sum_{i=1}^{k}a_{2023-t_i} \leq 506.$$Thus, we have that $$\left | \sum_{i=1}^{k}a_{t_i} \right | = - \sum_{i=1}^{k}a_{t_i} = \sum_{i=1}^{k}a_{2023-t_i} \leq 506,$$as desired.
Therefore, we have that for any maximal $\{t_i\}$, $$\left | \sum_{i=1}^{k}a_{t_i} \right | \leq 506,$$so for any $\{t_i\}$, $$\left | \sum_{i=1}^{k}a_{t_i} \right | \leq 506,$$implying that $C\leq 506$.
To show that $C=506$ works, do the following. Consider any sequence $a_i$. Without loss of generality, suppose that $a_i$ has at least as many $+1$'s as $-1$'s, since if there were at least as many $-1$'s as $+1$'s, we can take $b_i = -a_i$ which would have at least as many $+1$'s as $-1$'s, and $|\sum_{i=1}^{k}b_{t_i}| = |\sum_{i=1}^{k}-a_{t_i}| = |\sum_{i=1}^{k}a_{t_i}|$, so if $|\sum_{i=1}^{k}b_{t_i}| \geq 506$ for some $t_i$, then $|\sum_{i=1}^{k}a_{t_i}|\geq 506$ for the same $t_i$. Thus, we can safely assume without loss of generality that there are at least as many $+1$'s as $-1$'s. Suppose that there were $x$ $+1$'s and $2022-x$ $-1$'s for some $x\geq 1011$. Then, suppose that the indices for which the $a_k$'s are $-1$ were $c_1 < c_2 < \cdots < c_{2022-x}$. Then, let $\{t_i\}$ be every integer in $\{1, 2, \cdots, 2022\} \setminus \{c_1, c_3, \cdots \}$ in order, where $\{c_1, c_3, \cdots \}$ is the set of all $c_{2i+1}$. Such a $t_i$ is valid (i.e. satisfies the constraints of the problem) becuase obviously it is ordered, and since $c_{2i-1} < c_{2i} < c_{2i+1}$, we have that $c_{2i+1} - c_{2i-1} \geq 2$, so for any two consecutive terms, they are either $1$ apart or $2$ apart (one of the $c_{2i-1}$'s is between them), since no two $c_{2i-1}$'s can be between them since none of the $c_{2i-1}$'s are consecutive. Then, we have that since there are at least $\frac{2022-x}{2}$ odd numbers in $\{1, 2, \cdots, 2022-x\}$, there are at least $\frac{2022-x}{2}$ such $c_{2i+1}$'s, so
\begin{align*}
\sum_{i=1}^{k}a_{t_i} &= \sum_{i=1}^{2022}a_i - \sum a_{c_{2i+1}} \\
&= x - (2022 - x) - \sum a_{c_{2i+1}} \\
&= (2x-2022) - \sum a_{c_{2i+1}} \\
&\geq (2x-2022) - (-1)\cdot \frac{2022-x}{2} \\
&= \frac{3}{2}x - 1011 \\
&\geq \frac{3}{2}\cdot 1011 - 1011 \\
&= 505.5,
\end{align*}so since all the $a_{t_i}$'s are integers, $$\sum_{i=1}^{k}a_{t_i} \geq 506.$$Thus, we have that $$\left | \sum_{i=1}^{k}a_{t_i}\right | = \sum_{i=1}^{k}a_{t_i} \geq 506,$$as desired.
Thus, we have shown that we must have $C\leq 506$ and that $C = 506$ works, so we're done. $\blacksquare$
peace09
14.07.2023 21:50
Solved with pi271828. The answer is $506$. Let $S$ denote the sum in question; we seek the minimum of $\max(|S|)$ over all sequences $a_1,\dots,a_{2022}$. Optimality. Consider the sequence $1,-1,-1,1,1,\dots,1,1,-1$, and specifically the middle $2020$ terms; by symmetry, we can maximize the raw value of $S$ (rather than minimizing it and so maximizing its absolute value). If only one of the two terms $a_{4n-1},a_{4n}=1$ are among the chosen $a_{t_1},\dots,a_{t_k}$, we can include the other of the two whilst preserving all conditions and incrementing $S$. Additionally, for any "block" $-1,-1,1,1$ adjacent to but not among the chosen terms, we can include the terms $-1,1,1$ whilst preserving conditions and incrementing $|S|$. Including $a_1=1$, we therefore have the "steady state" \[S\le1-1+1+1-1+1+1-\dots-1+1+1=506,\]as claimed. Sufficiency. For any sequence, let $r_1,\dots,r_m$ denote the lengths of contiguous blocks of consecutive $-1$'s, and define $b_1,\dots,b_n$ similarly. To maximize the magnitude of $S$ in the negative direction, we include all the $-1$'s from $r_1,\dots,r_m$, and "bridge" these disjoint blocks with every other $1$, of which there are $\textstyle\sum\lfloor\tfrac{b_i}{2}\rfloor$. Analogously, to maximize the magnitude of $S$ in the positive direction, we include all the $1$'s from $b_1,\dots,b_n$ and bridge with every other $-1$, of which there are $\textstyle\sum\lfloor\tfrac{r_i}{2}\rfloor$. Hence, \[|S|_1=\sum_{i=1}^mr_i-\sum_{i=1}^n\left\lfloor\frac{b_i}{2}\right\rfloor\quad\text{and}\quad|S|_2=\sum_{i=1}^nb_i-\sum_{i=1}^m\left\lfloor\frac{r_i}{2}\right\rfloor\]are both attainable. Summing, we have \[|S|_1+|S|_2=\left(\sum_{i=1}^mr_i+\sum_{i=1}^nb_i\right)-\left(\sum_{i=1}^n\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\left\lfloor\frac{r_i}{2}\right\rfloor\right)\ge2022-1011=1011,\]whence one of $|S|_1,|S|_2$ are $\ge506$, as desired. $\square$
JAnatolGT_00
19.07.2023 19:30
We claim the answer $C=506.$ By a straightforward check the exact bound is obtained for the sequence $$+1,-1,-1,+1,+1,-1,-1,\ldots ,+1,+1,-1.$$ Now let's prove that such a sum is attainable for an arbitrary sequence. Divide the sequence in ascending order of index by consecutive blocks of equal numbers, and let these blocks contain $x_1,y_1,x_2,y_2,\ldots ,x_n,y_n$ numbers respectively ($x_i$ belongs to the block of $+1;$ probably $x_1$ or $y_n$ equal to $0$). Multiplying each number by $-1$ doesn't change the condition, so WLOG $\sum_{i=1}^n y_i\leq 1011.$ As a strategy lets pick all $+1,$ and in each block of $-1$ pick all numbers with even positions in this block - the sum of picked elements is $\sum_{i=1}^n \left( x_i-\left\lfloor \frac{y_i}{2}\right\rfloor \right) \geq 2022-\sum_{i=1}^n y_i -\left\lfloor \sum_{i=1}^n \frac{y_i}{2} \right\rfloor \geq 2022-1011-505=506.$
GreenTea2593
30.07.2023 06:02
ike.chen wrote: 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.$$ isn't it supposed to be $i=1$ instead of $i+1$ in the sigma notation? \[\left| \sum_{i=1}^{k} a_{t_i} \right| \geqslant C.\]
Attachments:
awesomeming327.
03.08.2023 06:49
The answer is $506$ with construction is $+,-,-,+$ $505$ times and $+,-$ in addition. In each $+,-,-,+$ and $-,+,+,-$ we can get at most $1$ in absolute value so the construction works. $~$ Now to show the bound, suppose WLOG there are at least $1011$ $+$. Select all the $+$, and every other $-$ then it's easy to show that we have at least $506$.
Inconsistent
09.08.2023 21:40
Answer $506$ from taking $-1, 1, 1, -1, -1, 1, 1, \ldots$. To prove notice that we can process each block of consecutive $+1$ or $-1$ so that if $x, y$ are the number of $+1, -1$ total then we have on a fixed sequence: $\max \text{LHS} \geq \max(x - y/2, y - x/2) \geq \frac{x+y}{4} = 505 \frac{1}{2}$, so $\max \text{LHS} \geq 506$. This constant is achieved by the construction via the same blocking logic so we are done.
asdf334
20.12.2023 04:09
Assume there are $a$ of the $+1$ and $b$ of the $-1$. Then $a+b=2022$. Let's now try to find the worst possible configuration for a fixed $a$ and $b$. To maximize $C$, realize that we are limited by the number of $-1$ we can remove. Turns out when all the $-1$ are consecutive this is the worst possible (there are equivalent configurations, but calculations will be the same.) Analogously all the $1$s are consecutive. From this logic we've proven both (1) guaranteed maximums and minimums and (2) provided the construction, say, $1,1,1,\dots,-1,-1,-1$. Now realize that the maximum is $M=a-b+\left \lceil \frac{b}{2}\right \rceil$ and the minimum is $m=a-b-\left \lceil \frac{a}{2}\right \rceil$. \[M+(-m)=\left \lceil \frac{a}{2}\right \rceil + \left \lceil \frac{b}{2}\right \rceil\]which is equal to $1011$ when $a$ is even. When $a$ is odd it's equal to $1012$. So we can always get at least $506$ difference.
jelena_ivanchic
13.01.2024 13:32
We claim that the answer is $\boxed{506}$.
Claim: $506$ is the upper bound.
Proof: 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 as nothing better can be achieved.
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.$$
Leo.Euler
18.01.2024 22:53
The answer is $\boxed{506}$. Construction is to take $1, -1, -1, 1$ repeatedly $505$ times and append $1, -1$. WLOG, suppose that there are at least $1011$ positive terms and at most $1011$ negative terms among the $a_i$. Break the sequence of $a_i$ into blocks of $1$s and $-1$s, so that the signs of the blocks alternate. If we let $x_1$, $x_2$, ... denote the sequence of negative block sizes, then the number of negative terms in the subsequence $a_{t_i}$ is at most \[ \sum \left\lfloor x_i/2 \right\rfloor \le \left\lfloor (x_1+x_2+\dots)/2 \right\rfloor \le 505, \]so adding in all of the positive terms yields that $C \le 506$ always.
SnowPanda
01.02.2024 03:02
The answer is $506$. To prove that $506$ is an upper bound, consider the $\pm 1$-sequence \[\underbrace{+1, \, +1, \, \ldots, \, +1}_{1011}, \, \underbrace{-1, \, -1, \, \ldots, \, -1}_{1011}.\]Then our subsequence $a_{t_i}$ must have at most $1011$ terms of $+1$ and at least $505$ terms of $-1$, so $\sum a_{t_i} \leq 1011 - 505 = 506$; similarly $\sum a_{t_i} \geq -506$.
Now we show that $506$ is always attainable. Without loss of generality suppose that there are at least as many $+1$'s as $-1$'s, so there are at least $1011$ $+1$'s and at most $1011$ $-1$'s. Then choose our subsequence $a_{t_i}$ to consist of all the $+1$'s, and alternating $-1$'s starting with the second --- for example, given the sequence $+1$, $-1$, $+1$, $+1$, $-1$, $-1$, $-1$, $+1$, $-1$, $+1$, $+1$, $+1$, we'd take the blue and red terms in $\textcolor{blue}{+1}$, $-1$, $\textcolor{blue}{+1}$, $\textcolor{blue}{+1}$, $\textcolor{red}{-1}$, $-1$, $\textcolor{red}{-1}$, $\textcolor{blue}{+1}$, $-1$, $\textcolor{blue}{+1}$, $\textcolor{blue}{+1}$, $\textcolor{blue}{+1}$. Then our subsequence has at least $1011$ $+1$'s and at most $505$ $-1$'s, so its sum is at least $506$.
Shreyasharma
07.02.2024 22:02
We will work the wording provided during the US IMO Training Camp. We claim that the answer is $\boxed{506}$. Upper Bound Proof. Consider the arrangement, \begin{align*} \text{RBBRRBB \dots RRB} \end{align*}Clearly it is optimal for Sally to begin on a ``block" of red buckets as if she begins on blue, she may just shift one ``block" back. Thus say she attempts to maximize $\text{Red} - \text{Blue}$. It is clear that in any block of four buckets, Sally can achieve a score of at most $+1$. As there are at most $506$ such sets, Sally can guarantee a score of at most $506$. $\square$ Lower Bound Proof. To show that Sally can always guarantee a score of $506$ take a random sequence. Assume that there are at most $1011$ blue buckets and at least $1011$ red buckets. Then say that there are ``blocks" of red buckets $r_1$, $r_2$, \dots, $r_x$ and blocks of blue buckets $b_1$, $b_2$, \dots $b_{x-1}$. Then the problem becomes the following. Pick an initial block $r_i$ to begin at, and a block $r_j$ to end at. Define the function $S(i, j) = \sum_{m=i}^j r_m - \sum_{m=i}^{j-1} \left\lfloor \frac{b_m}{2} \right\rfloor$ Maximize $S(a, b)$. Note that we may bound, \begin{align*} \sum_{m = i}^{j-1} \left\lfloor \frac{b_m}{2} \right\rfloor \leq \left\lfloor \frac{\sum_{m=1}^{x-1} b_m}{2} \right\rfloor \leq \left\lfloor \frac{1011}{2} \right\rfloor = 505 \end{align*}Then we guarantee at least, \begin{align*} S(1, x) \geq \sum_{m=1}^{x} r_m - 505 \geq 1011 - 505 = 506 \end{align*}and hence we are done. $\square$
mathboy100
19.02.2024 23:58
The answer is $506$. Define $f(S, C)$ for subsequence $S$ and $C \in {1, -1}$ to be the sum of the lengths of consecutive subsequences of $C$ in subsequence $S$ minus the sum of the floors of half of the length of each consecutive subsequence of $-C$ in subsequence $S$. It is obvious that the problem is asking for the minimum value of the maximum value of $C$ over every subsequence of every possible $\pm 1$ sequence. Observe that if $x$ is the number of $1$s in a subsequence, and $y$ is the number of $-1$s in a subsequence, then $f(S, 1) \geq x - \frac{y}{2}$, and $f(S, -1) \geq y - \frac{x}{2}$. Adding the two, we obtain $f(S, 1) + f(S, -1) \geq \frac{x+y}{2}$, so one of the function values must be greater than or equal to $\frac{x+y}{4}$. In particular, if our subsequence is the entire sequence, we must have a function value greater than or equal to $506$. Now, we claim that the sequence $1, -1, -1, 1, 1, -1, -1, \ldots -1$ satisfies the conditions. Observe that both $f(S, 1)$ and $f(S, -1)$ are equal to $506$ when $S$ is the full sequence. The rest of the proof that this sequence works is just casework, and I will omit it because I am lazy.
Mogmog8
28.04.2024 07:28
We claim the answer is $506$, which can be achieved by $505$ repetitions of $1,1,-1,-1$ followed by $1,-1$. For the bound, WLOG there are $a\le 1011$ negative ones. Then, in each consecutive group of negative ones we can eliminate at least half of them so there are at most $\lfloor a/2\rfloor$ negative ones left. Hence, the sum is at least $2022-a-\lfloor a/2\rfloor\ge 506$, as desired. $\square$
sami1618
12.05.2024 01:32
The answer is $\boxed{506}$. Construction: WLOG assume that there are at least $1011$ $a_i$ equal to $1$. Then over each gap of $a$ consecutive $a_i$ equal to $-1$ we can choose all but $\lfloor\frac{a}{2}\rfloor$ of them. So there exists a sequence with at least $1011$ positive $a_i$ and at most $505$ negative $a_i$. Bound: Consider the sequence $1,-1,-1,1,1,\dots,-1,-1,1,1,-1$. Each middle gap is 'unavoidable' leading to the desired bound.
Nuterrow
29.07.2024 00:44
Proof: We claim that the answer is $506$. Note that if we have more $-1$'s than $+1$'s, we can flip the signs of all the numbers without affecting the problem. For the upper bound, we just consider the sequence, $$+1 - 1 - 1 + 1 +1 -1 -1 \dots$$Now for the lower bound, suppose the number of $+1$'s in each block is $a_i$ from $a_1$ through $a_n$ and similarly the number of $-1$'s in each block is $b_i$ from $b_1$ through $b_m$. Our strategy will be to pick all the $+1$'s and pick as few $-1$'s as possible. For each block of $-1$ we will end up picking $\left \lfloor{\frac{b_i}{2}} \right \rfloor$ and thus, $$C \geq \sum_{i=1}^n a_i - \left(\sum_{i=1} \left \lfloor{\frac{b_i}{2}} \right \rfloor \right)$$$$C \geq \sum_{i=1}^n a_i - \left \lfloor {\frac{\sum_{i=1}^m b_i}{2}} \right \rfloor$$$$C \geq 1011 - 505 = 506$$
SomeonesPenguin
13.08.2024 22:50
The answer is $506$. For the construction take $$1,-1,-1,1,1,-1,-1,\dots,-1,-1,1,1,-1$$ Where the sequence $1,-1,-1,1$ is repeated $505$ times and at the end we add $1$ and $-1$. Now we show that we can always achieve $506$. Suppose that $1$ appears $a$ times and $-1$ appears $b$ times. Case 1. $a=b=1011$. Suppose the last number is negative and suppose the first one is positive (if it is not positive than just deleting the first negative numbers from the sequence gives a weaker problem). So consider the sequence $a_{1},a_{2},\dots,a_{2021}$. Now choose $t_i$ by this algorithm: Pick $t_{1}=1$. After this, if we have chosen $t_1,t_2,\dots,t_k$ and $a_{t_k+1} = 1$ pick $t_{k+1}=t_k+1$ and if $a_{t_k+1}=-1$ pick $t_{k+1}=t_k+2$. Notice that by doing this, we pick all the $1$s and skip at least $505$ of the $-1$s so the overall sum is at least $506$. Case 2. $a\neq b$. Suppose that $a > b$. We have that $a \ge 1012 > 1010 \ge b$ so by repeating the same algorithm from the start (without forgetting about the last number) we can choose every positive number and skip at least $\left\lfloor\frac{b}{2}\right\rfloor$ negative numbers so the sum will be at least $a-\left\lceil\frac{b}{2}\right\rceil\ge 1012-505=507$.
laura0105_somali
19.08.2024 21:56
2022 C1 Ex. Ex. the extreme version found here
onyqz
16.09.2024 20:23
posting for storage
We will show that the answer is $C=506$.
For the construction we can also take $$+1, +1, +1, \dots, +1, -1, -1, -1, \dots, -1 \, ,$$with $1011$ consecutive $+1$s and $1011$ consecutive $-1$s.
Now we show that we can always have $\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge 506$.
Obviously, one of $+1$ or $-1$ is $1011$ times or more in this sequence, WLOG let it be $+1$. Now split our sequence into blocks, each block only consisting of $-1$ or only consisting of $+1$. Now if the length $x$ of a $+1$-block is even, then we can take $\frac{x}{2}$ of these $+1$ (take the first, third, fifth, ... $+1$ of this block), satisfying our restriction $t_{i+1}-t_i \geq 2$. If $x$ is odd, then we can even take $\left\lceil \frac{x}{2} \right\rceil$ of these $+1$. Thus, since we initially assumed $\geq 1011$ of $+1$, we can take $\ge 506$ of them and hence $\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge 506$. $\square$
ezpotd
29.09.2024 04:05
I claim the answer is $506$. Construction with $506$ as maximal: $xxyyxxyyxxyy \cdots xxyyxy$, where $x$ represents $1$ and $y$ represents $-1$. The largest possible positive sum is accomplished when all positive elements are in the sequence, and we are forced to take $505$ negative elements since there are $505$ blocks of $2$ negative elements, this gives a sum of $1011 - 505 = 506$. Proof that we can always get $506$: Without loss of generality let there be at least as many positive elements as negative ones. Separate the sequence into blocks of positive and negative elements, we can take all the elements in positive blocks and we can ensure we take at most half of the elements in the negative blocks, so letting there be $x$ positive elements we can guarantee as a sum of at least $x - (\frac{2022 - x}{2}) = \frac 32 x - 1011$, since $x \ge 1011$ we have we can guarantee a sum at least $505.5$, since the sum is an integer we can guarantee $506$.
Bonime
29.10.2024 04:22
Ps: For some reason, AOPS won't let me post the solution to this problem in English, so it will be in Portuguese. Primeiro, observe que a resposta é $\boxed{506}$ e pode ser facilmente obtida pelo seguinte padrão: $$+--++--++--++...--++-$$ Agora, para provar o limite, vamos supor, SPG, que a quantidade de $a_i=+1$ é $\ge a_j=-1$ Seja $X_i$ o $i$-ésimo bloco composto de $x_i$ $a_j=+1$ e $Y_i$ o $i$-ésimo bloco composto de $y_i$ $a_j=-1$ Observe que para cada $\pm1$-sequência, podemos executar o seguinte algoritmo para obter $\sum_{i = 1}^{k} a_{t_i} \ge 506.$ Tome $(t_1, t_2, ..., t_{x_1})=X_1$ e $(t_{x_1+1}, t_{x_1+2}, ..., t_{x_1+\left \lfloor{\frac{y_1}{2}}\right \rfloor})$ alternadamente entre os termos de $Y_1$ começando com $t_{x_1+1}=a_{x_1+2}$. Mais especificamente, para cada $X_i$, tome todos os seus termos como elementos do conjunto ${a_{t_1}, a_{t_2}, ..., a_{t_k}}$ e, para cada $Y_i$, tome alternadamente seus valores como termos desse conjunto. Portanto, veja que isso pode ser feito já que a maior distância entre dois $t_i$s é $2$. Além disso, com este algoritmo, garantimos que: $$\sum_{i = 1}^{k} a_{t_i} \ge \sum_i x_i + \sum_i {\left \lfloor{\frac{y_i}{2}}\right \rfloor} \ge 1011-505=506$$Como queríamos mostrar.
sansgankrsngupta
17.11.2024 18:13
is $t_{k+1}= t_1$?
eibc
28.12.2024 01:32
The answer is $C = 506$. For a construction, take the sequence $+1, +1, \ldots, +1, -1, \ldots, -1$, consisting of $1011$ terms of $+1$ followed by $1011$ terms of $-1$. To prove bound holds, suppose WLOG there are more terms which are $+1$ than $-1$. Let $x$ be the number of terms which are $+1$. Now, suppose that whenever we come across a run of consecutive $-1$s, we only take the second term in the run to be one of the $a_{t_i}$, and then the fourth term, and so on. Then at most $\lfloor \tfrac{2022 - x}{2}\rfloor$ of the $a_{t_i}$ will be $-1$, so the sum of $a_{t_i}$ across all $1 \le i \le k$ is at least $x - \lfloor \tfrac{2022 - x}{2}\rfloor$. Since $x \ge 1011$ we have $\lfloor \tfrac{2022 - x}{2}\rfloor \le \tfrac{2022 - 1011}{2} = 505$, so $x - \lfloor \tfrac{2022 - x}{2}\rfloor \ge 1011 - 505 = 506.$
AshAuktober
01.01.2025 11:27
Warning: Super long writeup.
$\boxed{506}.$
Part 1: Optimality.We find a sequence for which $$S = \left| \sum_{i = 1}^{k} a_{t_i} \right| \le 506 \implies C \le 506.$$In particular, consider the sequence
$$-, +, +, -,-,+,+,-,-,+,+,\dots, -,-,+,$$Where the first term is $-1$ and then we alternate between groups of 2 plusses and two minuses.
Assume for the sake of contradiction that we can get $\sum_{i = 1}^{k} a_{t_i} \le -507$ somehow (if we can find $\sum_{i = 1}^{k} a_{t_i} \ge 507$, consider the sequence with reversed indices (i. e. $t_i \to 2023 - t_i$) to get $S \ge -507$, as then all terms become their negatives.
We have two cases:
Case 1: $t_1 = 1$.
We consider the range of this sequence, that is, $a_{t_k} - a_1$. Assume that $a_{t_k} = -1, a_{t_k+1} = 1$ WLOG.
Let $t_k$ then equal $4k+1$.
Then we have $m$ groups of plusses between $a_1, a_{t_k}$. Since we must have at least one plus per group in our sequence (else the condition on the boundedness of the differences of $t_i$ is contradicted), their contribution to $S$ is $\ge m$. Now, we can assume WLOG all minuses are covered within $[a_1, a_{t_k}]$; the number of such minuses is in fact $2m+1$, so the contribution to the score is $-2m-1$. Thus, $$S \ge -2m-1+m = -m-1.$$But note that $m \le 505 \implies S \ge -506$, which is what we wanted.
Case 2: $t_1 \ne 1$.
Say, yet again, our sequence's range has $m$ blocks of ones, and WLOG let the two smallest and two largest elements in this range be negative.
Then $S$, from similar calculation, is at least $-2(m+1) + m = -m-2$. But here we have $m \le 504$ (the leftmost group of plusses aren't countable in the range), so $S \ge -506$ yet again as desired.
Part 2: Achievability.We claim that there exists a sequence as given so that $$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge 506.$$Consider the following algorithm $A$:
Positive frog wrote:
Start with $t_1 = j$ with $j$ minimal, $a_j > 0$.. If $t_i + 1$ is positive, let $t_{i+1} = t_i + 1$, else let $t_{i+1} = t_i + 2$.
and the opposite algorithm $B$:
Negative frog wrote:
Start with $t_1 = j$ with $j$ minimal, $a_j < 0$. If $t_i + 1$ is negative, let $t_{i+1} = t_i + 1$, else let $t_{i+1} = t_i + 2$.
Let there be $r$ groups of length $b_1, b_2, \dots, b_r$ respectively.
Note that one algorithm gives us $$S \ge \sum_{2 \nmid i} m_i - \sum_{2 \mid j} \left\lfloor \frac{m_j}{2} \right \rfloor,$$while the other one gives us $$S \ge \sum_{2 \mid i}m_i - \sum_{2 \nmid j} \lfloor \frac{m_j}{2} \rfloor$$. Therefore, the average value of $S$ over these algorithms is at least
$$\frac{\sum_{i} m_i - \lfloor\frac{m_i}{2}\rfloor}{2} = \frac{\sum_{i} \lceil \frac{m_i}{2}\rceil}{2} \ge \frac{\sum_{i} \frac{m_i}{2}}{2} = \frac{2022}{4} = 505.5.$$Since the average of $S$ for these two algorithms is $505.5$ we must indeed have one of these algorithms from which $S \ge 505.5 \implies S \ge 506$, as desired. $\square$
lelouchvigeo
03.01.2025 16:54
$506$ works
Let $x$ and $y$ be the number of $+1's$ and $-1's$ respectively. WLOG assume $x \geq y$. Since due to our given condition that $t_{i+1} - t_i \le 2$ , we can choose all the $+1$ terms and a minimum number of $-1$ terms, dues to which our sum is atleast $1011 - \left\lfloor\frac{1011}{2}\right\rfloor \geq 506 $.
Now to prove that the lower bound is 506 consider the sequence $+--++--+...+--++-$