Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 8.8 Shortlist Prove it Taiwan

Determine the maximum positive integer LL such that there exist a sequence a1,a2,,aLa_1, a_2, \dots, a_L of positive integers satisfying:
(a) every term in the sequence is less than or equal to 220242^{2024};
(b) there does NOT exist a consecutive subsequence ai,ai+1,,aja_i, a_{i+1}, \dots, a_j (where 1ijL1 \le i \le j \le L) with a choice of signs si,si+1,,sj{1,1}s_i, s_{i+1}, \dots, s_j \in \{-1, 1\} for which
siai+si+1ai+1++sjaj=0. s_i a_i + s_{i+1} a_{i+1} + \dots + s_j a_j = 0.

Solution

The answer is 2202512^{2025}-1; in general, for an upper bound of 2k2^k, the maximum L=2k+11L = 2^{k+1}-1.

Construction: Let v2(x)v_2(x) denote the power of 22 in xx, and take ai=2kv2(i)a_i = 2^{k-v_2(i)}. Clearly ai2ka_i \le 2^k. Moreover, we have:

Lemma: For any 1ij2k+111 \le i \le j \le 2^{k+1}-1, there exists a unique ixji \le x \le j such that v2(x)=maxiyjv2(y)v_2(x) = \max_{i \le y \le j} v_2(y).

Proof: If both xx and yy attain the maximum value vv, this means x=p×2vx = p \times 2^v and y=q×2vy = q \times 2^v, where pp and qq are odd, and without loss of generality assume p<qp < q. But then, we have p<p+1<qp < p+1 < q, so z=(p+1)×2vz = (p+1) \times 2^v lies between xx and yy, but v>0v > 0, contradicting the maximality of vv.

Now, for any 1ij2k+111 \le i \le j \le 2^{k+1}-1, there exists a unique ixji \le x \le j such that v2(x)v_2(x) is maximal. This means v2(ax)=kvv_2(a_x) = k-v but v2(ay)>kvv_2(a_y) > k-v for all yxy \ne x, and hence v2(sa)=kvv_2(\sum s_\ell a_\ell) = k-v, so it cannot be 00.

Estimate: Suppose L2k+1L \ge 2^{k+1}. Suppose a1,,aLa_1, \dots, a_L satisfy ai2ka_i \le 2^k. Let b0=0b_0 = 0, and recursively define
si={+1if bi10,1if bi11. s_i = \begin{cases} +1 & \text{if } b_{i-1} \le 0, \\ -1 & \text{if } b_{i-1} \ge 1. \end{cases}
bi=bi1+siai. b_i = b_{i-1} + s_i a_i.

Now, consider the sequence b0,b1,,bLb_0, b_1, \dots, b_L. Note that, since ai2ka_i \le 2^k, if bi1[2k+1,0]b_{i-1} \in [-2^k+1, 0], then bi=bi1+ai[2k+1,2k]b_i = b_{i-1}+a_i \in [-2^k+1, 2^k]; conversely, if bi1[1,2k]b_{i-1} \in [1, 2^k], then bi=bi1ai[2k+1,2k]b_i = b_{i-1}-a_i \in [-2^k+1, 2^k]. Therefore, b0b_0 through bLb_L consist of L+12k+1+1L+1 \ge 2^{k+1}+1 terms in total, yet there are only 2k+12^{k+1} possible values, so there exist 1ijL1 \le i \le j \le L such that bi1=bjb_{i-1} = b_j, that is, bjbi1=jsa=0b_j - b_{i-1} = \sum_{\ell \le j} s_\ell a_\ell = 0. Hence there does not exist a sequence of length greater than 2k+112^{k+1}-1 satisfying the condition.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.