IMO 2019 Shortlisted Problems

Solution 1. Without loss of generality, assume ${\sum }_{i\in X}{a}_i⩽1$, and we may assume strict inequality as otherwise $b_i=a_i$ works. Also, $X$ clearly cannot be empty. If $n\in X$, add $\Delta$ to $a_n$, producing a sequence of $c_i$ with ${\sum }_{i\in X}{c}_i={\sum }_{i\in X^c}{c}_i$, and then scale as described above to make the sum equal to $2$. Otherwise, there is some $k$ with $k\in X$ and $k+1\in X^c$. Let $\delta =a_{k+1}-a_k$. - If $\delta >\Delta$, add $\Delta$ to $a_k$ and then scale. - If $\delta <\Delta$, then considering $X\cup \{k+1\}\backslash \{k\}$ contradicts $X$ being $(a_i)$-minimising. - If $\delta =\Delta$, choose any $j\ne k,k+1$ (possible since $n⩾3$), and any $ϵ$ less than the least of $a_1$ and all the differences $a_{i+1}-a_i$. If $j\in X$ then add $\Delta -ϵ$ to $a_k$ and $ϵ$ to $a_j$, then scale; otherwise, add $\Delta$ to $a_k$ and $ϵ/2$ to $a_{k+1}$, and subtract $ϵ/2$ from $a_j$, then scale.

---

Alternative solution.

Solution 2. This is similar to Solution 1, but without scaling. As in that solution, without loss of generality, assume ${\sum }_{i\in X}{a}_i<1$. Suppose there exists $1⩽j⩽n-1$ such that $j\in X$ but $j+1\in X^c$. Then $a_{j+1}-a_j⩾\Delta$, because otherwise considering $X\cup \{j+1\}\backslash \{j\}$ contradicts $X$ being $(a_i)$-minimising. If $a_{j+1}-a_j>\Delta$, put $$b_i=\{\begin{array}{ll}{a}_j+\Delta /2,& \text{ if }i=j\\ a_{j+1}-\Delta /2,& \text{ if }i=j+1\\ a_i,& \text{ otherwise }\end{array}$$ If $a_{j+1}-a_j=\Delta$, choose any $ϵ$ less than the least of $\Delta /2,a_1$ and all the differences $a_{i+1}-a_i$. If $|X|⩾2$, choose $k\in X$ with $k\ne j$, and put $$b_i=\{\begin{array}{ll}{a}_j+\Delta /2-ϵ,& \text{ if }i=j\\ a_{j+1}-\Delta /2,& \text{ if }i=j+1\\ a_k+ϵ,& \text{ if }i=k\\ a_i,& \text{ otherwise }\end{array}$$ Otherwise, $|X^c|⩾2$, so choose $k\in X^c$ with $k\ne j+1$, and put $$b_i=\{\begin{array}{ll}{a}_j+\Delta /2,& \text{ if }i=j;\\ a_{j+1}-\Delta /2+ϵ,& \text{ if }i=j+1;\\ a_k-ϵ,& \text{ if }i=k;\\ a_i,& \text{ otherwise. }\end{array}$$ If there is no $1⩽j⩽n$ such that $j\in X$ but $j+1\in X^c$, there must be some $1<k⩽n$ such that $X=[k,n]$ (certainly $X$ cannot be empty). We must have $a_1>\Delta$, as otherwise considering $X\cup \{1\}$ contradicts $X$ being $(a_i)$-minimising. Now put $$b_i=\{\begin{array}{ll}{a}_1-\Delta /2,& \text{ if }i=1\\ a_n+\Delta /2,& \text{ if }i=n\\ a_i,& \text{ otherwise }\end{array}$$

---

Alternative solution.

Solution 3. Without loss of generality, assume ${\sum }_{i\in X}{a}_i⩽1$, so $\Delta ⩾0$. If $\Delta =0$ we can take $b_i=a_i$, so now assume that $\Delta >0$. Suppose that there is some $k⩽n$ such that $|X\cap [k,n]|>|X^c\cap [k,n]|$. If we choose the largest such $k$ then $|X\cap [k,n]|-|X^c\cap [k,n]|=1$. We can now find the required sequence $(b_i)$ by starting with $c_i=a_i$ for $i<k$ and $c_i=a_i+\Delta$ for $i⩾k$, and then scaling as described above. If no such $k$ exists, we will derive a contradiction. For each $i\in X$ we can choose $i<j_i⩽n$ in such a way that $j_i\in X^c$ and all the $j_i$ are different. (For instance, note that necessarily $n\in X^c$ and now just work downwards; each time an $i\in X$ is considered, let $j_i$ be the least element of $X^c$ greater than $i$ and not yet used.) Let $Y$ be the (possibly empty) subset of $[1,n]$ consisting of those elements in $X^c$ that are also not one of the $j_i$. In any case $$\Delta =\sum _{i\in X}\left(a_{j_i}-a_i\right)+\sum _{j\in Y}{a}_j$$ where each term in the sums is positive. Since $n⩾3$ the total number of terms above is at least two. Take a least such term and its corresponding index $i$ and consider the set $Z$ which we form from $X$ by removing $i$ and adding $j_i$ (if it is a term of the first type) or just by adding $j$ if it is a term of the second type. The corresponding expression of $\Delta$ for $Z$ has the sign of its least term changed, meaning that the sum is still nonnegative but strictly less than $\Delta$, which contradicts $X$ being $(a_i)$-minimising.

---

Alternative solution.

Solution 4. This uses some similar ideas to Solution 3, but describes properties of the index sets $X$ that are sufficient to describe a corresponding sequence $(b_i)$ that is not derived from $(a_i)$. Note that, for two subsets $X,Y$ of $[1,n]$, the following are equivalent: - $|X\cap [i,n]|⩽|Y\cap [i,n]|$ for all $1⩽i⩽n$; - $Y$ is at least as large as $X$, and for all $1⩽j⩽|Y|$, the $j^{\text{th}}$ largest element of $Y$ is at least as big as the $j^{\text{th}}$ largest element of $X$; - there is an injective function $f:X\to Y$ such that $f(i)⩾i$ for all $i\in X$. If these equivalent conditions are satisfied, we write $X\le Y$. We write $X<Y$ if $X\le Y$ and $X\ne Y$. Note that if $X\prec Y$, then ${\sum }_{i\in X}{a}_i<{\sum }_{i\in Y}{a}_i$ (the second description above makes this clear). We claim first that, if $n⩾3$ and $X\prec X^c$, then there exists $Y$ with $X\prec Y\prec X^c$. Indeed, as $|X|⩽|X^c|$, we have $|X^c|⩾2$. Define $Y$ to consist of the largest element of $X^c$, together with all but the largest element of $X$; it is clear both that $Y$ is distinct from $X$ and $X^c$, and that $X\le Y\le X^c$, which is what we need. But, in this situation, we have $$\sum _{i\in X}{a}_i<\sum _{i\in Y}{a}_i<\sum _{i\in X^c}{a}_i\text{ and }1-\sum _{i\in X}{a}_i=-\left(1-\sum _{i\in X^c}{a}_i\right),$$ so $\left|1-{\sum }_{i\in Y}{a}_i\right|<\left|1-{\sum }_{i\in X}{a}_i\right|$. Hence if $X$ is $(a_i)$-minimising, we do not have $X<X^c$, and similarly we do not have $X^c<X$. Considering the first description above, this immediately implies the following Claim. Claim. There exist $1⩽k,\ell ⩽n$ such that $|X\cap [k,n]|>\frac{n-k+1}{2}$ and $|X\cap [\ell ,n]|<\frac{n-\ell +1}{2}$. We now construct our sequence $(b_i)$ using this claim. Let $k$ and $\ell$ be the greatest values satisfying the claim, and without loss of generality suppose $k=n$ and $\ell <n$ (otherwise replace $X$ by its complement). As $\ell$ is maximal, $n-\ell$ is even and $|X\cap [\ell ,n]|=\frac{n-\ell }{2}$. For sufficiently small positive $ϵ$, we take $$b_i=iϵ+\{\begin{array}{ll}0,& \text{ if }i<\ell \\ \delta ,& \text{ if }\ell ⩽i⩽n-1\\ \gamma ,& \text{ if }i=n\end{array}$$ Let $M={\sum }_{i\in X}i$. So we require $$Mϵ+\left(\frac{n-\ell }{2}-1\right)\delta +\gamma =1$$ and $$\frac{n(n+1)}{2}ϵ+(n-\ell )\delta +\gamma =2$$ These give $$\gamma =2\delta +\left(\frac{n(n+1)}{2}-2M\right)ϵ$$ and for sufficiently small positive $ϵ$, solving for $\gamma$ and $\delta$ gives $0<\delta <\gamma$ (since $ϵ=0$ gives $\delta =1/\left(\frac{n-\ell }{2}+1\right)$ and $\gamma =2\delta$), so the sequence is strictly increasing and has positive values.