IMO 2016 Shortlisted Problems

Answer. $n$ can be any odd integer greater than or equal to $3$.

For any even integer $n⩾4$, we consider the case $$a_1=a_2=\cdots =a_{n-1}=b_n=0\text{and}{b}_1=b_2=\cdots =b_{n-1}=a_n=1.$$ The condition $\left|a_k\right|+\left|b_k\right|=1$ is satisfied for each $1⩽k⩽n$. No matter how we choose each $x_k$, both sums ${\sum }_{k=1}^n{x}_k{a}_k$ and ${\sum }_{k=1}^n{x}_k{b}_k$ are odd integers. This implies $\left|{\sum }_{k=1}^n{x}_k{a}_k\right|⩾1$ and $\left|{\sum }_{k=1}^n{x}_k{b}_k\right|⩾1$, which shows (1) cannot hold.

For any odd integer $n⩾3$, we may assume without loss of generality $b_k⩾0$ for $1⩽k⩽n$ (this can be done by flipping the pair $\left(a_k,b_k\right)$ to $\left(-a_k,-b_k\right)$ and $x_k$ to $-x_k$ if necessary) and $a_1⩾a_2⩾\cdots ⩾a_m⩾0>a_{m+1}⩾\cdots ⩾a_n$. We claim that the choice $x_k=(-1{)}^{k+1}$ for $1⩽k⩽n$ will work. Define $$s=\sum _{k=1}^m{x}_k{a}_k\text{and}t=-\sum _{k=m+1}^n{x}_k{a}_k$$ Note that $$s=\left(a_1-a_2\right)+\left(a_3-a_4\right)+\cdots ⩾0$$ by the assumption $a_1⩾a_2⩾\cdots ⩾a_m$ (when $m$ is odd, there is a single term $a_m$ at the end, which is also positive). Next, we have $$s=a_1-\left(a_2-a_3\right)-\left(a_4-a_5\right)-\cdots ⩽a_1⩽1$$ Similarly, $$t=\left(-a_n+a_{n-1}\right)+\left(-a_{n-2}+a_{n-3}\right)+\cdots ⩾0$$ and $$t=-a_n+\left(a_{n-1}-a_{n-2}\right)+\left(a_{n-3}-a_{n-4}\right)+\cdots ⩽-a_n⩽1.$$ From the condition, we have $a_k+b_k=1$ for $1⩽k⩽m$ and $-a_k+b_k=1$ for $m+1⩽k⩽n$. It follows that ${\sum }_{k=1}^n{x}_k{a}_k=s-t$ and ${\sum }_{k=1}^n{x}_k{b}_k=1-s-t$. Hence it remains to prove $$|s-t|+|1-s-t|⩽1$$ under the constraint $0⩽s,t⩽1$. By symmetry, we may assume $s⩾t$. If $1-s-t⩾0$, then we have $$|s-t|+|1-s-t|=s-t+1-s-t=1-2t⩽1$$ If $1-s-t⩽0$, then we have $$|s-t|+|1-s-t|=s-t-1+s+t=2s-1⩽1$$ Hence, the inequality is true in both cases.

These show $n$ can be any odd integer greater than or equal to $3$.

---

Alternative solution.

The even case can be handled in the same way as Solution 1. For the odd case, we prove by induction on $n$.

Firstly, for $n=3$, we may assume without loss of generality $a_1⩾a_2⩾a_3⩾0$ and $b_1=a_1-1$ (if $b_1=1-a_1$, we may replace each $b_k$ by $-b_k$).

- Case 1. $b_2=a_2-1$ and $b_3=a_3-1$, in which case we take $(x_1,x_2,x_3)=(1,-1,1)$. Let $c=a_1-a_2+a_3$ so that $0⩽c⩽1$. Then $|b_1-b_2+b_3|=|a_1-a_2+a_3-1|=1-c$ and hence $|c|+|b_1-b_2+b_3|=1$.

- Case 2. $b_2=1-a_2$ and $b_3=1-a_3$, in which case we take $(x_1,x_2,x_3)=(1,-1,1)$. Let $c=a_1-a_2+a_3$ so that $0⩽c⩽1$. Since $a_3⩽a_2$ and $a_1⩽1$, we have $$c-1⩽b_1-b_2+b_3=a_1+a_2-a_3-1⩽1-c.$$ This gives $|b_1-b_2+b_3|⩽1-c$ and hence $|c|+|b_1-b_2+b_3|⩽1$.

- Case 3. $b_2=a_2-1$ and $b_3=1-a_3$, in which case we take $(x_1,x_2,x_3)=(-1,1,1)$. Let $c=-a_1+a_2+a_3$. If $c⩾0$, then $a_3⩽1$ and $a_2⩽a_1$ imply $$c-1⩽-b_1+b_2+b_3=-a_1+a_2-a_3+1⩽1-c$$ If $c<0$, then $a_1⩽a_2+1$ and $a_3⩾0$ imply $$-c-1⩽-b_1+b_2+b_3=-a_1+a_2-a_3+1⩽1+c.$$ In both cases, we get $|-b_1+b_2+b_3|⩽1-|c|$ and hence $|c|+|-b_1+b_2+b_3|⩽1$.

- Case 4. $b_2=1-a_2$ and $b_3=a_3-1$, in which case we take $(x_1,x_2,x_3)=(-1,1,1)$. Let $c=-a_1+a_2+a_3$. If $c⩾0$, then $a_2⩽1$ and $a_3⩽a_1$ imply $$c-1⩽-b_1+b_2+b_3=-a_1-a_2+a_3+1⩽1-c.$$ If $c<0$, then $a_1⩽a_3+1$ and $a_2⩾0$ imply $$-c-1⩽-b_1+b_2+b_3=-a_1-a_2+a_3+1⩽1+c.$$ In both cases, we get $|-b_1+b_2+b_3|⩽1-|c|$ and hence $|c|+|-b_1+b_2+b_3|⩽1$.

We have found $x_1,x_2,x_3$ satisfying (1) in each case for $n=3$.

Now, let $n⩾5$ be odd and suppose the result holds for any smaller odd cases. Again we may assume $a_k⩾0$ for each $1⩽k⩽n$. By the Pigeonhole Principle, there are at least three indices $k$ for which $b_k=a_k-1$ or $b_k=1-a_k$. Without loss of generality, suppose $b_k=a_k-1$ for $k=1,2,3$. Again by the Pigeonhole Principle, as $a_1,a_2,a_3$ lies between $0$ and $1$, the difference of two of them is at most $\frac{1}{2}$. By changing indices if necessary, we may assume $0⩽d=a_1-a_2⩽\frac{1}{2}$.

By the inductive hypothesis, we can choose $x_3,x_4,\dots ,x_n$ such that $a^{\prime }={\sum }_{k=3}^n{x}_k{a}_k$ and $b^{\prime }={\sum }_{k=3}^n{x}_k{b}_k$ satisfy $|a^{\prime }|+|b^{\prime }|⩽1$. We may further assume $a^{\prime }⩾0$.

- Case 1. $b^{\prime }⩾0$, in which case we take $(x_1,x_2)=(-1,1)$. We have $|-a_1+a_2+a^{\prime }|+|-(a_1-1)+(a_2-1)+b^{\prime }|=|-d+a^{\prime }|+|-d+b^{\prime }|⩽\max \{a^{\prime }+b^{\prime }-2d,a^{\prime }-b^{\prime },b^{\prime }-a^{\prime },2d-a^{\prime }-b^{\prime }\}⩽1$ since $0⩽a^{\prime },b^{\prime },a^{\prime }+b^{\prime }⩽1$ and $0⩽d⩽\frac{1}{2}$.

- Case 2. $0>b^{\prime }⩾-a^{\prime }$, in which case we take $(x_1,x_2)=(-1,1)$. We have $|-a_1+a_2+a^{\prime }|+|-(a_1-1)+(a_2-1)+b^{\prime }|=|-d+a^{\prime }|+|-d+b^{\prime }|$. If $-d+a^{\prime }⩾0$, this equals $a^{\prime }-b^{\prime }=|a^{\prime }|+|b^{\prime }|⩽1$. If $-d+a^{\prime }<0$, this equals $2d-a^{\prime }-b^{\prime }⩽2d⩽1$.

- Case 3. $b^{\prime }<-a^{\prime }$, in which case we take $(x_1,x_2)=(1,-1)$. We have $|a_1-a_2+a^{\prime }|+|(a_1-1)-(a_2-1)+b^{\prime }|=|d+a^{\prime }|+|d+b^{\prime }|$. If $d+b^{\prime }⩾0$, this equals $2d+a^{\prime }+b^{\prime }<2d⩽1$. If $d+b^{\prime }<0$, this equals $a^{\prime }-b^{\prime }=|a^{\prime }|+|b^{\prime }|⩽1$.

Therefore, we have found $x_1,x_2,\dots ,x_n$ satisfying (1) in each case. By induction, the property holds for all odd integers $n⩾3$.