Determine the maximal length $L$ of a sequence $a_1,\dots,a_L$ of positive integers satisfying both the following properties: every term in the sequence is less than or equal to $2^{2023}$, and there does not exist a consecutive subsequence $a_i,a_{i+1},\dots,a_j$ (where $1\le i\le j\le L$) with a choice of signs $s_i,s_{i+1},\dots,s_j\in\{1,-1\}$ for which \[s_ia_i+s_{i+1}a_{i+1}+\dots+s_ja_j=0.\]
Problem
Source: ISL 2023 C2
Tags: combinatorics
17.07.2024 15:24
Buffed version: replace $2^{2023}$ with any positive integer $n$.
17.07.2024 16:34
The answer is \( L = 2^{2024} - 1 \). Next, we will demonstrate that there exists a sequence of length \( 2^{2024} - 1 \) that satisfies the conditions. We will proceed with mathematical induction on \( n \), where \( a_i \leqslant 2^n \), showing that there exists a sequence of length \( 2^{n+1} - 1 \) that satisfies this condition. 1. Base case: Considering \( n = 1 \), a sequence of length \( 2^2 - 1 = 3 \) is possible. Clearly, the sequence \( 2, 1, 2 \) satisfies this. 2. Inductive step: Let \( a_1, a_2, \dots, a_{2^n-1} \) be a sequence that satisfies \( a_i \leqslant 2^{n-1} \). Consider the sequence: - Double each element: \( 2a_1, 2a_2, \dots, 2a_{2^n-1} \) denoted as \( A \). - Append \( 1 \) after \( A \). - Reverse \( A \) and append it again after \( 1 \). Denote this sequence as \( B \).$$\underbrace{2a_1,2a_2,\dots,2a_{2^n-1}}_A,1,\underbrace{2a_{2^n-1},\dots,2a_2,2a_1}_B$$ It can be shown that every term in the sequence \( A \cup \{1\} \cup B \) is less than or equal to \( 2 \cdot 2^{n-1} = 2^n \). If there exists a subsequence \( k_i, k_{i+1}, \dots, k_j \) in \( A \) such that \( s_i k_i + s_{i+1} k_{i+1} + \dots + s_j k_j = 0 \), then: \[ s_i \left( \frac{k_i}{2} \right) + s_{i+1} \left( \frac{k_{i+1}}{2} \right) + \dots + s_j \left( \frac{k_j}{2} \right) = 0 \]which contradicts the assumption from the induction hypothesis of case \( n-1 \). Similarly, if such a subsequence exists in \( B \), it contradicts the assumption from the induction hypothesis of case \( n-1 \). Therefore, the subsequence must include \( 1 \), which clearly contradicts the assumption because the sum of an odd number with an even number cannot be \( 0 \). Thus, the sequence defined above has a length of \( 2^{n+1} - 1 \) and satisfies the condition. 3. Conclusion: Therefore, if \( a_i \leqslant 2^{2023} \), there exists a sequence of length \( 2^{2024} - 1 \). Next, we will demonstrate that there is no sequence of length \( 2^{2024} \) that satisfies the above conditions. Consider \( a_1, a_2, \dots, a_{2^{2024}} \). We will demonstrate by finding contradictions, assuming that there is no \( \pm a_i \pm a_{i+1} \dots \pm a_{j} = 0 \), when \( 1 \leqslant i \leqslant j \leqslant 2^{2024} \).$$b_{i+1}=\left\{\begin{array}{l}{b_i - a_{i+1}\text{ if }b_i>0}\\{b_i + a_{i+1}\text{ if }b_i<0}\end{array}\right.$$ By considering the sequence \( b_i \), which is defined by \( b_1 = a_1 \) and for any integer \( i \) where \( 1 \leqslant i \leqslant 2^{2024} \), it is easy to see that: \[ b_i = s_1 a_1 + s_2 a_2 + s_3 a_3 + \dots + s_i a_i \]where \( s_1, s_2, \dots, s_i \in \{1, -1\} \), defined by \( s_k = \text{sgn}(b_{k-1}) \) for all integers \( k \) where \( 1 < k \leq i \), and \( s_1 = 1 \). We can observe that for every \( i \), it holds that \( -(2^{2023} - 1) \leq b_i \leq 2^{2023} \). Since: \[ -(2^{2023} - 1) \leq b_i \leq 2^{2023} \] The possible values of \( b_i \) are: \[ -(2^{2023} - 1), -(2^{2023} - 2), \dots, -1, 1, 2, \dots, 2^{2023} \] There are \( 2^{2024} \) possible values for \( b_i \). However, the sequence \( b_i \) consists of \( 2^{2024} \) elements. By the pigeonhole principle, at least two numbers in the sequence \( b_i \) must be equal. Suppose \( b_s \) and \( b_t \) are equal, where \( s < t \). Then: \[ b_t - b_s = 0 \Rightarrow s_{s+1} a_{s+1} + s_{s+2} a_{s+2} + \dots + s_t a_t = 0 \] This contradicts our earlier assumption that there is no subsequence \( \pm a_i \pm a_{i+1} \dots \pm a_{j} = 0 \). Therefore, we can conclude that there does not exist a sequence of length \( 2^{2024} \) that satisfies the conditions outlined.
17.07.2024 16:42
The answer is $L = 2^{k+1}-1$ where $2023$ is replaced by $k$. Call a consecutive subsequence $a_i, a_{i+1}, \ldots, a_j$ bad if there exist $s_i, s_{i+1}, \ldots, s_j\in\{-1, 1\}$ such that \[a_is_i+a_{i+1}s_{i+1}+\ldots+a_js_j=0.\]The construction for $L = 2^{k+1} - 1$ is by induction: start with the sequence $s_1 = 1$ for $k=1$ and construct the sequence $s_{k+1}$ as $2\cdot s_k, 1, 2\cdot s_k$ (that is, $s_{k+1}$ is two copies of the elements of $s_k$, multiplied by $2$, separated by a $1$). If $s_k$ has no bad subsequence, so does $s_{k+1}$ due to parity and the induction hypothesis on the two copies of $s_k$. To prove $L = 2^k$ doesn't work, we fix signs for each $a_i$ by focusing on the prefixes. That is, we start by picking $s_1 = 1$ and then pick $s_{i+1}$ depending on the previously picked $s_1, s_2, \ldots, s_i$, adhering to the following rules: If $a_1s_1+a_2s_2+\ldots+a_is_i < 2^{k}$, then $s_{i+1} = 1$. Else, $s_{i+1} = -1$. Note that at any point, the prefix sum $c_i = a_1s_1+a_2s_2+\ldots+a_is_i$ is non-negative and strictly less than $2^{k+1}$ as $1\leq a_i\leq 2^k$. Therefore, there exists an index $i$ with $c_i=0$, which corresponds to a bad subsequence, or two indices $i<j$, such that $c_i=c_j$. However, $c_j - c_i = 0$, so $a_i, a_{i+1}, \ldots, a_j$ is a bad subsequence, and we're done once again. This finishes.
19.07.2024 07:20
The answer is $2^{n+1}-1$ where we replace $2023$ with $n$. The construction is the same as the ones provided above.
22.07.2024 04:36
Since no one has posted the solution to the buffed version yet, I will. If we replace $2^{2023}$ with general $n$, the answer is $L=2^{k+1}-1$ where $k=\lfloor\log_2 n\rfloor$. Construction for $\boldsymbol{n=2^k}$ and $\boldsymbol{L=2^{k+1}-1}$ We take $a_i=2^{k-\nu_2(i)}$. For example, if $k=3$, then the sequence is $$8\ 4\ 8\ 2\ 8\ 4\ 8\ \textbf 1\ 8\ 4\ 8\ 2\ 8\ 4\ 8.$$To see why this works, note that the subsequence cannot go through $1$ in the middle (otherwise, the sum is odd). Thus, it must be strictly within the left half or the right half. However, each half is the construction for $k-1$ multiplied by $2$, so we can repeat this argument to realize that no subsequence and signing work. Bound for $\boldsymbol{n=2^{k+1}-1}$ and $\boldsymbol{L=2^{k+1}}$ We use induction on $k$. The base case $k=0$ is clear. For the inductive step, the idea is to consider the partial sums $s_i = a_1+a_2+\dots+a_i$ (and $s_0=0$). We have $2^{k+1}+1$ of these, so by Pigeonhole, at least $2^k+1$ of these have the same parity. This means that we can split group the numbers into $2^k$ blocks so that each block has even sum. For example, if if $L = 8$ and $s_1$, $s_3$, $s_4$, $s_5$, $s_8$ have the same parity, then the blocks are $(a_2\ a_3)\ (a_4)\ (a_5)\ (a_6\ a_7\ a_8)$. Within each block, we may choose $\pm$ signs so that the results is in $[0, 2^{k+1}-2]$ (by choosing one by one and maintain that interval). If any of these were $0$, we are done. Otherwise, we divide the result of each block by $2$. We then get $2^k$ numbers in $[1, 2^k-1]$, and so we can use the induction hypothesis for $k-1$. Done.
29.07.2024 03:45
Replace $2023$ with $n$. We claim the answer is $L=2^{n+1}-1$. First, we consider the following sequences of integers $A_0,A_1, \ldots$ \[ A_0=1 \]\[ A_1=2, 1, 2 \]\[ A_2=4, 2, 4, 1, 4, 2, 4\]\[ A_3=8, 4, 8, 2, 8, 4, 8, 1, 8, 4, 8, 2, 8, 4, 8 \]\[ \cdots \]To get from $A_k$ to $A_{k+1}$, we slot $2^{k+1}$ between any pair of numbers, as well as the two ends. We claim that $A_n$ is our desired equality case for $L=2^{n+1}-1$. First, we note that $A_n$ has length $2^{n+1}-1$ and has no entries exceeding $2^n$. Notice that in this construction, given any consecutive instances of $2^m$, the entry at their midpoint is strictly less than $2^m$. Thus, given any contiguous block $B$ in $A_n$, the minimal element appears exactly once. So, we cannot partition $B$ into two multisets with equal sum, since the multiset with the unique minimum in $B$ will have a sum with a strictly lower $\nu_2$. Now, all that is left to show is that $L \geq 2^{n+1}$ has such a contiguous block. AFTOC that no such block exists. Consider a sequence $e_1,e_2, \ldots, e_L \in \{-1,1\}$ with the following inductive definition \[ e_k = \begin{cases} 1 & \text{if } e_1a_1+e_2a_2+ \cdots e_ka_k \leq 0\\ -1 & \text{otherwise} \end{cases} \] It follows that $|e_1a_1+\cdots +e_ka_k| \leq 2^n$ for all $k \leq L$. By our assumption, $e_1a_1+\cdots +e_ka_k \not = 0$ for any $k$. Moreover, if $k \geq 2$ and $e_1a_1+\cdots +e_ka_k = \pm 2^n$ then $e_1a_1+\cdots +e_{k-1}a_{k-1} = 0$ which contradicts our assumption. Thus, if we consider the set $S$ denoting all possible values of $e_1a_1+\cdots +e_ka_k$ we see that $0 \not \in S$ and at least one of $2^n$ or $-2^n$ are not in $S$. Thus, $|S| \leq 2^{n+1}-1$ implying by PHP that some $d \in S$ appears at least \[ \left \lceil \frac{2^{n+1}}{|S|} \right \rceil \geq 2 \]times in $S$. Thus, there is some $i<j$ where \[ e_1a_1+\cdots +e_ia_i = e_1a_1+\cdots +e_ja_j = d \]but then, \[ e_{i+1}a_{i+1}+ \cdots +e_ja_j =0 \]Contradicting our assumption. $\blacksquare$
29.07.2024 07:26
We claim the answer is $2^{n+1} - 1$ for general $2^n$. The construction follows by making $\nu_2(a_i) = n - \nu_2(i)$. For example, when $n = 3$, we get construction $8\:4\:8\:2\:8\:4\:8\:1\:8\:4\:8\:2\:8\:4\:8$. One can see that either $i \le j < 8$ or $8 < i \le j$, since otherwise, the sum would have exactly one factor of $2$ which presents a contradiction. This split the construction into two halves. So divide by $2$ for the remaining halves and repeat the argument. We will use induction to prove the bound, with the base case of $n = 1$ not being hard to see as the maximal sequence is $2, 1, 2$. We will now assume that for any $2^{n-1}$ positive integers less than $2^{n-2}$, there will be a consecutive subsequence that can be made into $0$ and prove that any sequence of length $2^{n}$ has a subsequence that can be made into $0$. Let the positions of the odd terms be $a_{n_1}, a_{n_2}, \ldots, a_{n_k}$ where $\{n_i\}_{i=1}^k$ is an increasing sequence. We can combine terms $a_{n_{2k-1}}, \ldots, a_{n_{2k}}$, picking signs to ensure that $|e_{n_{2k-1}}a_{n_{2k-1} + \cdots + e_{n_{2k}}a_{n_{2k}}}| \le 2^{n-1}$. If it is $0$, we have found a subsequence, so assume not. Now we get that the all terms are even. So divide by $2$ and apply the inductive hypothesis. If there are not enough terms, consider combining terms $a_{n_{2k}}, \ldots, a_{n_{2k+1}}$ instead and now this is guaranteed to have at least $2^{n-1}$ terms, so we are done by induction.
09.08.2024 22:05
The answer is $2^{n+1}-1$ in general (numbers are less than $2^{n}$).
19.08.2024 16:17
The answer is $\boxed{2^{2024}-1}$, achieved by the sequence $a_k=2^{2023-\nu_2(k)}$. To prove that $2^{2024}$ is impossible, consider starting from $0$, and for each new term in the sequence, either adding or subtracting it to stay within $[-(2^{2023}-1),2^{2023}]$. Note that if we ever repeat a number or get to $0$, we lose, because then we just found a substring that works. But there are only $2^{2024}-1$ nonzero numbers in this interval, contradiction. $\blacksquare$
18.11.2024 04:04
The answer is $2^{2024}-1$. For any sequence $a_1, \dots, a_L$, define $b_i$ for $0 \leq i \leq L$ and $s_i$ for $1 \leq i \leq L$ as follows: $b_0=0, s_i = \begin{cases} 1 & \text{if } b_{i-1} \leq 0 \\ -1 &\text{if } b_{i-1}>0 \end{cases}, b_i=b_{i-1}+s_ia_i$ for $1 \leq i \leq L$. Note that if $b_i=b_j$ for some $i<j$, then $s_{i+1}a_{i+1} + \cdots + s_ja_j =0$. We claim that $-2^{2023} < b_i \leq 2^{2023}$ for all $i$. We prove this by induction. Clearly this is true for $i=0$. For $i>0$, if $b_{i-1} \leq 0$, that means $-2^{2023}<-2^{2023}+a_i<b_i=b_{i-1}+a_i \leq 0+2^{2023}=2^{2023}$. If $b_{i-1}>0$, $-2^{2023}=0-2^{2023}<b_i=b_{i-1}-a_i \leq 2^{2023}-a_i < 2^{2023}$, so we are done. Then, if $L+1>2^{2023}+2^{2023}=2^{2024}$, there must exist $b_i=b_j$ where $i<j$ by pigeonhole principle. So $L \geq 2^{2024}-1$. We now give a construction for $L=2^{2024}-1$. Put $a_i=2^{2023-\nu_2(i)}$ for $1 \leq L \leq 2^{2024}$. Assume there exists $i \leq j$, $s_i, \dots, s_j$ such that the sum $S=s_ia_i+ \cdots s_ja_j=0$. If $i \leq 2^{2023} \leq j$, then $S \equiv 1 \pmod{2}$, contradiction. Since $a_i=2^{2023-\nu_2(i)}=2^{2023-\nu_2(2^{2024}-i)}=a_{2^{2024}-i}$, we may WLOG assume $i,j <2^{2023}$. Then if $i \leq 2^{2022} \leq j$, then $S \equiv 2 \pmod{4}$, which is again a contradiction. $a_i=2^{2023-\nu_2(i)}=2^{2023-\nu_2(2^{2023}-i)}=a_{2^{2023}-i}$, so WLOG assume $i,j < 2^{2022}$. Inductively, we may show that $i,j<2^1$, so $i=j=1$, contradiction. So this construction works, so we are done. $\square$