Original Problem:

  1. 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?


1 Answer 1


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.

  • $\begingroup$ You prove that no even $n$ work by using a difinitive value of $a_k$ and $b_k$ which is a mistake. You must also consider the cases for all REAL values of $a$ and $b$ $\endgroup$
    – Hafizudeen
    Apr 19, 2017 at 12:35
  • $\begingroup$ It's not a mistake. Making all the numbers 1/2 and making x alternate between -1 and 1 satisfies the inequality for any n $\endgroup$
    – amakelov
    Apr 19, 2017 at 16:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .