IMO Shortlist, 2016

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

For any even integer $n \geqslant 4$, we consider the case
$$a_{1}=a_{2}=\cdots=a_{n-1}=b_{n}=0 \quad \text{and} \quad 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 \leqslant k \leqslant 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| \geqslant 1$ and $\left|\sum_{k=1}^{n} x_{k} b_{k}\right| \geqslant 1$, which shows (1) cannot hold.

For any odd integer $n \geqslant 3$, we may assume without loss of generality $b_{k} \geqslant 0$ for $1 \leqslant k \leqslant 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} \geqslant a_{2} \geqslant \cdots \geqslant a_{m} \geqslant 0>a_{m+1} \geqslant \cdots \geqslant a_{n}$. We claim that the choice $x_{k}=(-1)^{k+1}$ for $1 \leqslant k \leqslant n$ will work. Define
$$s=\sum_{k=1}^{m} x_{k} a_{k} \quad \text{and} \quad 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 \geqslant 0$$
by the assumption $a_{1} \geqslant a_{2} \geqslant \cdots \geqslant 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 \leqslant a_{1} \leqslant 1$$
Similarly,
$$t=\left(-a_{n}+a_{n-1}\right)+\left(-a_{n-2}+a_{n-3}\right)+\cdots \geqslant 0$$
and
$$t=-a_{n}+\left(a_{n-1}-a_{n-2}\right)+\left(a_{n-3}-a_{n-4}\right)+\cdots \leqslant-a_{n} \leqslant 1.$$
From the condition, we have $a_{k}+b_{k}=1$ for $1 \leqslant k \leqslant m$ and $-a_{k}+b_{k}=1$ for $m+1 \leqslant k \leqslant 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| \leqslant 1$$
under the constraint $0 \leqslant s, t \leqslant 1$. By symmetry, we may assume $s \geqslant t$. If $1-s-t \geqslant 0$, then we have
$$|s-t|+|1-s-t|=s-t+1-s-t=1-2 t \leqslant 1$$
If $1-s-t \leqslant 0$, then we have
$$|s-t|+|1-s-t|=s-t-1+s+t=2 s-1 \leqslant 1$$
Hence, the inequality is true in both cases.

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

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} \geqslant a_{2} \geqslant a_{3} \geqslant 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 \leqslant c \leqslant 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 \leqslant c \leqslant 1$. Since $a_{3} \leqslant a_{2}$ and $a_{1} \leqslant 1$, we have
$$c-1 \leqslant b_{1}-b_{2}+b_{3}=a_{1}+a_{2}-a_{3}-1 \leqslant 1-c.$$
This gives $|b_{1}-b_{2}+b_{3}| \leqslant 1-c$ and hence $|c|+|b_{1}-b_{2}+b_{3}| \leqslant 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 \geqslant 0$, then $a_{3} \leqslant 1$ and $a_{2} \leqslant a_{1}$ imply
$$c-1 \leqslant-b_{1}+b_{2}+b_{3}=-a_{1}+a_{2}-a_{3}+1 \leqslant 1-c$$
If $c<0$, then $a_{1} \leqslant a_{2}+1$ and $a_{3} \geqslant 0$ imply
$$-c-1 \leqslant-b_{1}+b_{2}+b_{3}=-a_{1}+a_{2}-a_{3}+1 \leqslant 1+c.$$
In both cases, we get $|-b_{1}+b_{2}+b_{3}| \leqslant 1-|c|$ and hence $|c|+|-b_{1}+b_{2}+b_{3}| \leqslant 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 \geqslant 0$, then $a_{2} \leqslant 1$ and $a_{3} \leqslant a_{1}$ imply
$$c-1 \leqslant-b_{1}+b_{2}+b_{3}=-a_{1}-a_{2}+a_{3}+1 \leqslant 1-c.$$
If $c<0$, then $a_{1} \leqslant a_{3}+1$ and $a_{2} \geqslant 0$ imply
$$-c-1 \leqslant-b_{1}+b_{2}+b_{3}=-a_{1}-a_{2}+a_{3}+1 \leqslant 1+c.$$
In both cases, we get $|-b_{1}+b_{2}+b_{3}| \leqslant 1-|c|$ and hence $|c|+|-b_{1}+b_{2}+b_{3}| \leqslant 1$.

We have found $x_{1}, x_{2}, x_{3}$ satisfying (1) in each case for $n=3$.

Now, let $n \geqslant 5$ be odd and suppose the result holds for any smaller odd cases. Again we may assume $a_{k} \geqslant 0$ for each $1 \leqslant k \leqslant 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 \leqslant d=a_{1}-a_{2} \leqslant \frac{1}{2}$.

By the inductive hypothesis, we can choose $x_{3}, x_{4}, \ldots, x_{n}$ such that $a' = \sum_{k=3}^{n} x_{k} a_{k}$ and $b' = \sum_{k=3}^{n} x_{k} b_{k}$ satisfy $|a'|+|b'| \leqslant 1$. We may further assume $a' \geqslant 0$.

- Case 1. $b' \geqslant 0$, in which case we take $(x_{1}, x_{2})=(-1,1)$.
We have $|-a_{1}+a_{2}+a'|+|-(a_{1}-1)+(a_{2}-1)+b'|=|-d+a'|+|-d+b'| \leqslant \max \{a'+b'-2d, a'-b', b'-a', 2d-a'-b'\} \leqslant 1$ since $0 \leqslant a', b', a'+b' \leqslant 1$ and $0 \leqslant d \leqslant \frac{1}{2}$.

- Case 2. $0 > b' \geqslant -a'$, in which case we take $(x_{1}, x_{2})=(-1,1)$.
We have $|-a_{1}+a_{2}+a'|+|-(a_{1}-1)+(a_{2}-1)+b'|=|-d+a'|+|-d+b'|$. If $-d+a' \geqslant 0$, this equals $a'-b'=|a'|+|b'| \leqslant 1$. If $-d+a'<0$, this equals $2d-a'-b' \leqslant 2d \leqslant 1$.

- Case 3. $b'<-a'$, in which case we take $(x_{1}, x_{2})=(1,-1)$.
We have $|a_{1}-a_{2}+a'|+|(a_{1}-1)-(a_{2}-1)+b'|=|d+a'|+|d+b'|$. If $d+b' \geqslant 0$, this equals $2d+a'+b'<2d \leqslant 1$. If $d+b'<0$, this equals $a'-b'=|a'|+|b'| \leqslant 1$.

Therefore, we have found $x_{1}, x_{2}, \ldots, x_{n}$ satisfying (1) in each case. By induction, the property holds for all odd integers $n \geqslant 3$.