Maths Olympiad Prep

Library / /102 of 106

Combinatorics Difficulty 9.1 IMO level Prove it IMO

A ±1\pm 1-sequence is a sequence of 20222022 numbers a1,,a2022a_{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 \leqslant t_{1}<\ldots<t_{k} \leqslant 2022 so that ti+1ti2t_{i+1}-t_{i} \leqslant 2 for all ii, and
i=1katiC. \left|\sum_{i=1}^{k} a_{t_{i}}\right| \geqslant C.

Solution

First, we prove that this can always be achieved. Without loss of generality, suppose at least 20222=1011\frac{2022}{2}=1011 terms of the ±1\pm 1-sequence are +1+1. Define a subsequence as follows: starting at t=0t=0, if at=+1a_{t}=+1 we always include ata_{t} in the subsequence. Otherwise, we skip ata_{t} if we can (i.e. if we included at1a_{t-1} in the subsequence), otherwise we include it out of necessity, and go to the next tt. Clearly, this subsequence will include all +1+1s. Also, for each 1-1 included in the sequence, a 1-1 must have been skipped, so at most 10112=505\left\lfloor\frac{1011}{2}\right\rfloor=505 can be included. Hence the sum is at least 1011505=5061011-505=506, as desired.

Next, we prove that, for the ±1\pm 1-sequence
({1},{+1,+1},{1,1},{+1,+1},,{+1,+1},{1,1},{+1}) (\{-1\},\{+1,+1\},\{-1,-1\},\{+1,+1\}, \ldots,\{+1,+1\},\{-1,-1\},\{+1\})
each admissible subsequence atia_{t_{i}} has 506iati506-506 \leqslant \sum_{i} a_{t_{i}} \leqslant 506. We say that the terms inside each curly bracket is a block. In total, there are 10121012 blocks - 506506 of them hold +1+1s, and 506506 of them hold 1-1s. (The two blocks at each end hold 11 number each, each other block holds 22.)

Suppose an admissible subsequence includes terms from kk blocks holding +1+1s. Then, in each 1-1-pair in between the +1+1-pairs, the subsequence must also include at least one 1-1. There can be at most two +1+1s included from each +1+1-block, and at least one 1-1 must be included from each 1-1-block, so the sum is at most 2k(k1)=k+12k-(k-1)=k+1.

For k<506k<506, this is at most 506506. If k=506k=506, one of the +1+1-blocks must be the one at the end, meaning it can only include one +1+1, so that the maximum in this case is only kk, not k+1k+1, so in this case the sum is also at most 506506.

Hence we have shown that for any admissible subsequence, iati506\sum_{i} a_{t_{i}} \leqslant 506. Analogously we can show that 506iati-506 \leqslant \sum_{i} a_{t_{i}}, meaning that C506C \leqslant 506 as desired.

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 and solution reproduced as published; topic and difficulty added by this site.