Advance algebra problem Original Problem:


*

*Find all integers $n\geq 3$ with the following property: for all real numbers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ satisfying $|a_k|+|b_k|=1$ for $1\leq k \leq n,$ there exists $x_1, x_2, \ldots, x_n,$ each of which is either $-1$ or $1,$ such that 


$$\left| \sum_{k=1}^nx_ka_k\right|+\left| \sum_{k=1}^nx_kb_k\right|\leq 1.$$
I tried to use triangle inequality, rearrangement inequality, mean inequality and Cauchy-Schwartz inequality to solve this problem, by i still cant find a proper solution. Does anyone know how to answer this? 
 A: First, observe that no even $n$ works: if $n$ is even, take $a_1=1,a_2=\ldots=a_n=0$, and $b_1=0,b_2=\ldots=b_n=1$. Then clearly both sums $\sum_{k=1}^n x_ka_k$ and $\sum_{k=1}^nx_kb_k$ must be at least 1 in magnitude, because they're both odd integers - so the total sum is at least 2.
Next, one interesting observation is that if $n_1,\ldots,n_m$ and $m$ are all solutions, then so is $n_1+\ldots+n_m$. Indeed, suppose we have real numbers arranged into $m$-dimensional arrays $A$ and $B$ where the $i$-th row has length $n_i$, such that $|A_{ik}|+|B_{ik}|=1$ for all appropriate $i,k$. Then there exists an array $X$ of -1s and 1s of the same shape as $A$ and $B$ such that 
$$\left|\sum_{k=1}^{n_i} X_{ik}A_{ik}\right| + \left|\sum_{k=1}^{n_i}X_{ik}B_{ik} \right|\leq 1$$
for all $1\leq i\leq m$. Now we define new numbers 
$$A_i:=\sum_{k=1}^{n_i} X_{ik}A_{ik},\quad B_i:=\sum_{k=1}^{n_i} X_{ik}B_{ik} $$
for all $1\leq i\leq m$. Observe that $|A_i|+|B_i|\leq 1$ which means we can apply the $m$-case of our statement (note that the condition $|a_k|+|b_k|=1$ can be relaxed to $|a_k|+|b_k|\leq 1$ without loss of generality). Thus there exists a vector $Y\in\{-1,1\}^m$ such that 
$$\left| \sum_{i=1}^m Y_iA_i\right| + \left|\sum_{i=1}^m Y_iB_i\right|\leq 1 $$
and hence the numbers $\alpha_{ik}=Y_iX_{ik}$ give us a solution for the $n_1+\ldots+n_m$ case. 
Observe that the inequality is trivially true for $n=1$. Thus, if we prove that it works for $n=3$, we'd be able to show it works for all odd numbers by induction, writing $2k+1 = (2k-1) + 1 + 1$ as a sum of three numbers for which it works.
Thus, the only thing that remains is to prove the case $n=3$. To do that, we use the following geometric interpretation: we put the points $(a_1,b_1),(a_2,b_2),(a_3,b_3)$ in the plane (with $a_i$ on the $x$ axis and $b_i$ on the $y$ axis). Observe that without loss of generality we can assume that $a_i\geq 0$ because otherwise we can flip signs of $x_i$ and $b_i$ until we get the $a_i$ to be $\geq 0$. So now the three vectors $v_i=(a_i,b_i)$ lie in the $x\geq 0$ halfplane, and also lie on the 1-norm 1-ball $B=\{(a,b) : |a|+|b| = 1\}$.
One of them will be between the other two when you draw them, let that be $v_2$ WLOG, with $v_1$ above $v_2$ and $v_3$ below it. Then we claim that $x=(1,-1,1)$ works, which is equivalent to saying that $v_1+v_3-v_2$ is inside $B$. To see why, write 
$$v_1+v_3-v_2 = v_1+(v_3-v_2)$$
and at this point it's proof by picture according to the different cases for where $v_1,v_2,v_3$ are compared to the $x$-axis. 
