Maths Olympiad Prep

Library / /436 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

Find all integers n3n \geqslant 3 with the following property: for all real numbers a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and b1,b2,,bnb_{1}, b_{2}, \ldots, b_{n} satisfying ak+bk=1\left|a_{k}\right|+\left|b_{k}\right|=1 for 1kn1 \leqslant k \leqslant n, there exist x1,x2,,xnx_{1}, x_{2}, \ldots, x_{n}, each of which is either -1 or 1 , such that
k=1nxkak+k=1nxkbk1 \left|\sum_{k=1}^{n} x_{k} a_{k}\right|+\left|\sum_{k=1}^{n} x_{k} b_{k}\right| \leqslant 1
Answer. nn can be any odd integer greater than or equal to 3.

Solution

For any even integer n4n \geqslant 4, we consider the case
a1=a2==an1=bn=0 and b1=b2==bn1=an=1 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 ak+bk=1\left|a_{k}\right|+\left|b_{k}\right|=1 is satisfied for each 1kn1 \leqslant k \leqslant n. No matter how we choose each xkx_{k}, both sums k=1nxkak\sum_{k=1}^{n} x_{k} a_{k} and k=1nxkbk\sum_{k=1}^{n} x_{k} b_{k} are odd integers. This implies k=1nxkak1\left|\sum_{k=1}^{n} x_{k} a_{k}\right| \geqslant 1 and k=1nxkbk1\left|\sum_{k=1}^{n} x_{k} b_{k}\right| \geqslant 1, which shows (1) cannot hold.
For any odd integer n3n \geqslant 3, we may assume without loss of generality bk0b_{k} \geqslant 0 for 1kn1 \leqslant k \leqslant n (this can be done by flipping the pair (ak,bk)\left(a_{k}, b_{k}\right) to (ak,bk)\left(-a_{k},-b_{k}\right) and xkx_{k} to xk-x_{k} if necessary) and a1a2am0>am+1ana_{1} \geqslant a_{2} \geqslant \cdots \geqslant a_{m} \geqslant 0>a_{m+1} \geqslant \cdots \geqslant a_{n}. We claim that the choice xk=(1)k+1x_{k}=(-1)^{k+1} for 1kn1 \leqslant k \leqslant n will work. Define
s=k=1mxkak and t=k=m+1nxkak. 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=(a1a2)+(a3a4)+0 s=\left(a_{1}-a_{2}\right)+\left(a_{3}-a_{4}\right)+\cdots \geqslant 0
by the assumption a1a2ama_{1} \geqslant a_{2} \geqslant \cdots \geqslant a_{m} (when mm is odd, there is a single term ama_{m} at the end, which is also positive). Next, we have
s=a1(a2a3)(a4a5)a11 s=a_{1}-\left(a_{2}-a_{3}\right)-\left(a_{4}-a_{5}\right)-\cdots \leqslant a_{1} \leqslant 1
Similarly,
t=(an+an1)+(an2+an3)+0 t=\left(-a_{n}+a_{n-1}\right)+\left(-a_{n-2}+a_{n-3}\right)+\cdots \geqslant 0
and
t=an+(an1an2)+(an3an4)+an1. 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 ak+bk=1a_{k}+b_{k}=1 for 1km1 \leqslant k \leqslant m and ak+bk=1-a_{k}+b_{k}=1 for m+1knm+1 \leqslant k \leqslant n. It follows that k=1nxkak=st\sum_{k=1}^{n} x_{k} a_{k}=s-t and k=1nxkbk=1st\sum_{k=1}^{n} x_{k} b_{k}=1-s-t. Hence it remains to prove
st+1st1 |s-t|+|1-s-t| \leqslant 1
under the constraint 0s,t10 \leqslant s, t \leqslant 1. By symmetry, we may assume sts \geqslant t. If 1st01-s-t \geqslant 0, then we have
st+1st=st+1st=12t1 |s-t|+|1-s-t|=s-t+1-s-t=1-2 t \leqslant 1
If 1st01-s-t \leqslant 0, then we have
st+1st=st1+s+t=2s11 |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 nn can be any odd integer greater than or equal to 3.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.