The answer is all odd $n$. First Solution (mine): For even $n \ge 2$, one can conjure the following counterexample: set $a_1 = a_2 = \dots = a_{n-1} = 1$ and $a_n = 0$ (and $b_1 = \dots = b_{n-1} = 0$ and $b_n = 1$). In that case both terms of the inequality are odd integers, hence they have sum at least $2$. Now we prove odd positive integers are always possible. We will make the following simplifications: By negating $\{a_i, b_i\}$ in pairs, we may assume $a_i \ge 0$ for all $i$. By negating all $b_i$ at once, we may assume there are an odd number of positive $b_i$'s. Assume $a_1 < \dots < a_k$ correspond to positive $b_i$'s and $a_{k+1} < \dots < a_n$ correspond to negative $b_i$'s. We claim that we can take $\varepsilon_1 = +1$, $\varepsilon_2 = -1$, \dots, $\varepsilon_k = +1$ and $\varepsilon_{k+1} = +1$, $\varepsilon_{k+2} = -1$, \dots, $\varepsilon_n = -1$. Here is an example: \[ \begin{array}{c|rrrrr|rr} \varepsilon_i & +1 & -1 & +1 & -1 & +1 & +1 & -1 \\ \hline a_i & 0.1 & 0.2 & 0.4 & 0.6 & 0.8 & 0.3 & 0.6 \\ b_i & 0.9 & 0.8 & 0.6 & 0.4 & 0.2 & -0.7 & -0.4 \end{array} \]If one takes the four sums in the quadrant above, we in fact get four numbers as follows: \[ \begin{array}{r|r} \alpha & -\gamma \\ \hline \beta & -\gamma \end{array} \]where $\alpha+\beta=1$ and all three numbers are in $[0,1]$. Second Solution (geometric, outline): We just prove that odd $n$ work. As before assume $a_i > 0$, with an odd number of positive $b_i$'s and an even number of negative $b_i$'s. View the points as vectors in ${\mathbb R}^2$ lying on a ``tilted square''. Alternate signs on each vector now, along the boundary of the square. It's then not difficult to check that sum of the red arrows lies inside the square. [asy][asy]size(8cm); pair A = dir(90); pair B = dir(0); pair C = dir(-90); pair D = dir(180); draw(A--B--C--D--cycle, blue); draw(A--C, blue); draw(B--D, blue); pair P_1 = 0.3*B+0.7*A; pair P_2 = 0.5*B+0.5*A; pair P_3 = 0.8*B+0.2*A; pair P_4 = 0.9*B-0.1*A; pair P_5 = 0.7*B-0.3*A; pair P_6 = 0.45*B-0.55*A; pair P_7 = 0.15*B-0.85*A; pair O = origin; pen r = red + 1.2; draw( O--P_1, r, EndArrow(TeXHead)); draw(P_2--P_3, r, EndArrow(TeXHead)); draw(P_4--P_5, r, EndArrow(TeXHead)); draw(P_6--P_7, r, EndArrow(TeXHead)); label("$(0,1)$", A, A); label("$(1,0)$", B, B); label("$(0,-1)$", C, C); label("$(-1,0)$", D, D); dot(A); dot(B); dot(C); dot(D); dot("$P_1$", P_1, dir(45)); dot("$P_2$", P_2, dir(45)); dot("$P_3$", P_3, dir(45)); dot("$P_4$", P_4, dir(300)); dot("$P_5$", P_5, dir(300)); dot("$P_6$", P_6, dir(300)); dot("$P_7$", P_7, dir(300)); dot(O);[/asy][/asy]

We claim that the answer is all odd integers $n \ge 3$. Firstly, we show that for all even $n$, the statement is false. Let $a_{1} = 1, b_{1} = 0$ and $a_{i} = 0, b_{i} = 1$ for all $i \ge 2$. Then, $\left|\displaystyle\sum_{k = 1}^{n}x_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{n}x_{k}b_{k}\right| = |x_{1}| + |x_{2} + x_{3} + ... + x_{n}| \ge 2$ as both summands are nonnegative odd integers. Thus, we found a counterexample to the statement when $n$ is even. Now, suppose $n$ is odd. We may assume that $b_{i} \ge 0$ because if $b_{i} < 0$, we may flip the sign of $b_{i}$ along with the corresponding $a_{i}$ and then change $x_{i}$ accordingly. Introduce $n$ new variables $s_{1}, s_{2}, ..., s_{n} \in \{-1, 1\}$ such that if $a_{i} < 0$, $s_{i} = -1$ and $s_{i} = 1$ otherwise. Next, replace all negative $a_{i}$ with its absolute value. The problem condition can now be rewritten as $\left|\displaystyle\sum_{k = 1}^{n}x_{k}s_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{n}x_{k}b_{k}\right| \le 1$ where $s_{k} \in \{-1, 1\}$ and $a_{i}, b_{i}$ are nonnegative reals where $a_{i} + b_{i} = 1$ for all $1 \le i \le n$. Now, since $b_{i} = 1 - a_{i}$, we can rewrite the inequality as $\left|\displaystyle\sum_{k = 1}^{n}x_{k}s_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{n}x_{k} - \displaystyle\sum_{k = 1}^{n}x_{k}a_{k}\right| \le 1$. Lemma 1.1 : Given real numbers $d_{1} \le d_{2} \le ... \le d_{k}$ where $k \ge 1$ and $0 \le d_{i} \le 1$, we can partition them into two sets $D_{1}, D_{2}$ such that $|S(D_{1}) - S(D_{2})| \le d_{k}$ where $S(X)$ denotes the sum of all elements in a set $X$. Proof : We prove this claim by induction on $k$. The base case $k = 1$ is trivial. Suppose we already have a partition of $d_{1}, d_{2}, ..., d_{k}$ into two sets $D_{1}, D_{2}$ satisfying the conditions. WLOG, suppose $S(D_{1}) \le S(D_{2})$. Now, suppose we add another element $d_{k + 1}$ (which is the largest among $d_{1}, d_{2}, ..., d_{k + 1})$. We'll add it to the set $D_{1}$. By induction hypothesis, $S(D_{2}) - S(D_{1}) \le d_{k}$. We have $|S(D_{1}) - S(D_{2}) + d_{k + 1}| = S(D_{1}) + d_{k + 1} - S(D_{2}) \le d_{k + 1}$. This completes the inductive step. Lemma 1.2 : For all $n \ge 1$ and all $(a_{1}, a_{2}, ..., a_{n}) \in \mathbb{R}_{\ge 0}^{n}$, we can find $(x_{1}, x_{2}, ..., x_{n}) \in \{-1,1\}^{n}$ such that $\displaystyle\sum_{i = 1}^{n}x_{i} = X$, where $X = 0$ if $n$ is even and $X = 1$ if $n$ is odd, and $0 \le \displaystyle\sum_{i = 1}^{n}a_{i}x_{i} \le 1$. Proof : For $n = 1$, the claim is trivial, as we can just take $x_{1} = 1$. Thus, we now assume $n > 1$. WLOG, let $a_{1} \le a_{2} \le ... \le a_{n}$. Let $k = \lfloor\frac{n}{2}\rfloor$. Let $d_{i} = a_{2i} - a_{2i - 1}$ for all $1 \le i \le k$. By Lemma 1.1, we can partition the $d_{i}$ into two groups $D_{1}$, $D_{2}$ such that $|S(D_{1}) - S(D_{2})| \le d_{k}$. We swap $D_{1}$ and $D_{2}$ accordingly so that $S(D_{1}) \ge S(D_{2})$. If $n$ is even, assign $1$ to all the elements of $D_{1}$ and $-1$ to all the elements of $D_{2}$. Otherwise, assign $-1$ to all elements of $D_{1}$ and $1$ to all elements of $D_{2}$. If an element $d_{i}$ is assigned $1$, assign $x_{2i} = 1, x_{2i - 1} = -1$ and do the opposite for when $d_{i}$ is assigned $-1$. We can see that all conditions are satisfied if $n$ is even. If $n$ is odd, we can assign $x_{n} = 1$ so that the sum of all $x_{i}$ is $1$ and $\displaystyle\sum_{i = 1}^{n}a_{i}x_{i} = \displaystyle\sum_{i = 1}^{n - 1}a_{i}x_{i} + a_{n} = a_{n} - (S(D_{1}) - S(D_{2}))$. Since $0 \le S(D_{1}) - S(D_{2}) \le d_{k}$, $a_{n} \ge a_{n - 1} \ge a_{n - 1} - a_{n - 2} = d_{k}$, and $a_{n} \le 1$, we have the desired conclusion. Lemma 1.3 : For all real numbers $0 \le x, y \le 1$, we have $|x - y| + |1 - (x + y)| \le 1$. Proof : WLOG, let $x \ge y$. Then, there are two cases. Case 1 : $x + y \le 1$ Then, $|x - y| + |1 - (x + y)| = x - y + 1 - x - y = 1 - 2y \le 1$. Case 2 : $x + y \ge 1$ Then, $|x - y| + |1 - (x + y)| = x - y + x + y - 1 = 2x - 1 \le 1$. Back to the original problem, we need $\left|\displaystyle\sum_{k = 1}^{n}x_{k}s_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{n}x_{k} - \displaystyle\sum_{k = 1}^{n}x_{k}a_{k}\right| \le 1$. WLOG, we can assume that $s_{1} = s_{2} = ... = s_{l} = 1$ and $s_{l + 1} = ... = s_{n} = -1$. Now, $\left|\displaystyle\sum_{k = 1}^{n}x_{k}s_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{n}x_{k} - \displaystyle\sum_{k = 1}^{n}x_{k}a_{k}\right| = \left|\displaystyle\sum_{k = 1}^{l}x_{k}a_{k} - \displaystyle\sum_{k = l + 1}^{n}x_{k}a_{k}\right| + \left|\displaystyle\sum_{k = 1}^{l}x_{k} + \displaystyle\sum_{k = l + 1}^{n}x_{k} - \displaystyle\sum_{k = 1}^{l}x_{k}a_{k} - \displaystyle\sum_{k = l + 1}^{n}x_{k}a_{k}\right|$. Assume $l$ is even (the case where $l$ is odd is exactly the same). By Lemma 1.2, we can find $x_{i} \in \{-1, 1\}$ such that $0 \le \displaystyle\sum_{k = 1}^{l}x_{k}a_{k}, \displaystyle\sum_{k = l + 1}^{n}x_{k}a_{k} \le 1$, $\displaystyle\sum_{k = 1}^{l}x_{k} = 0$, $\displaystyle\sum_{k = l + 1}^{n}x_{k} = 1$. Let $S_{1} = \displaystyle\sum_{k = 1}^{l}x_{k}a_{k}$ and $S_{2} = \displaystyle\sum_{k = l + 1}^{n}x_{k}a_{k}$. We have $0 \le S_{1}, S_{2} \le 1$. Now, we claim that $|S_{1} - S_{2}| + |1 - (S_{1} + S_{2})| \le 1$, which will complete the proof. This follows from Lemma 1.3 and we're done.

For even $n$ choose $a_1 = a_2 = \dots = a_{n - 1} = 1$ and $a_n = 0$, with the corresponding $b_i$'s being either 0 or 1. Then each of the sums $\sum_{i = 1}^n \varepsilon_ia_i$ and $\sum_{i = 1}^n \varepsilon_ia_i$ is equal to some odd integer and thus the sum of their absolute values is at least 2. For odd $n$, regard the pairs $v_k = (a_k, b_k)$ as vectors on the square region $|x| + |y| = 1$. We wish to prove that there exists a choice of signs such that the vector $$v = \pm v_1 \pm v_2 \pm \dots \pm v_n$$ Lies on the region $|x| + |y| \leq 1$. For each $n$-tuple of vectors $V = (v_1, v_2, \dots, v_n)$ on the relevant region let $f(V)$ be the minimal posible value of the sum involved in the problem over all possible choices of $\varepsilon_1, \varepsilon_2, \dots, \varepsilon_n$ in $\{-1, 1\}^n$. Let $S = \{|x| + |y| = 1 \vert x, y \in \mathbb{R}\}$. Then $f \colon S^n \to \mathbb{R}$ is continuous and $S^n$ is compact, so there exists a choice of $V$ such that $f(V)$ is maximal, as $f$ is clearly bounded above by $2n$. We will prove $f(V) \leq 1$ for this choice of $V$. WLOG assume $a_i \geq 0$ everywhere by changing $v_k$ by $-v_k$ if necessary. Moreover assume that $v_i \neq (0, -1)$ everywhere by also flipping this vector if necessary. Consider a choice of $\{\varepsilon_i\}_{i = 1}^n$ such that $f(V)$ is minimal. Assume, reordering if necessary, that $\varepsilon_i = 1$ for $i = 1, 2, \dots, k$ and it is equal to $-1$ otherwise. Now assume that there are at least three $v_i$'s not equal to $(0, 1), (0 - 1)$ or $(1, 0)$. Then there exist two with the same value of $\varepsilon_i$. WLOG assume these are $v_1, v_2$ and that $a_1 \leq a_2$. If $a_1 \leq 1 - a_2$ then switch $v_1, v_2$ by $v_1' = (0, \pm 1)$ and $v_2' = (a_2 + a_1, b_2 + b_1 \mp 1)$ where the sign of the $y$ coordinate of $v_1'$ is the same as that of $v_1$. We have $a_1 + a_2 \leq 1$ and it's straightforward to verify that $-1 \leq b_2 + b_1 \pm 1 \leq 1$, so this is valid. If on the other hand $a_1 \geq 1 - a_2$ then choose instead $v_1' = (a_1 + a_2 - 1, b_1 + b_2)$ and $v_2 = (1, 0)$. It is easy to verify that $b_1 + b_2 \leq 1$ so this works. Note that both of these choices mantain $v_1 + v_2$, and thus by applying this process repeatedly we may obtain a configuration $V'$ where at most two $v_i$'s are different from $(0, -1), (0, 1), (1, 0)$ and the value of $f(V')$ is the minimal that may occur among any choice of $V$. Thus it now suffices to prove the problem is true when zero, one or two $v_i$'s are not one of the vectors mentioned before. Moreover we may assume $v_i \neq (0, -1)$ by switching $v_i$ by $-v_i$ if necessary. If no vector is different from $(0, 1)$ and $(1, 0)$ then as $n$ is odd, one of these choices appears an even number of times, so we may choose the signs such that the sum of these vectors is zero. The remaining vectors may then be assigned signs to give either $(0, 1)$ or $(1, 0)$. If exactly one vector is different from $(0, 1)$ and $(1, 0)$, then as $n - 1$ is even, the number of vectors of each of these two types have the same parity. If they are both even then we may arrange to get $(0, 0)$ and we're good no matter what the remaining vector is. Otherwise, assume by symmetry that the remaining vector has $x, y \geq 0$. Arrange the $(0, 1)$ and $(1, 0)$ vectors to obtain $(-1, -1)$, which is clearly possible. Upon adding the remaining vector we obtain something in the segment $\{x + y = -1 | x, y \leq 0\}$ which is contained in the region, so we're done. Now, if exactly two vectors are not $(1, 0)$ or $(0, 1)$, then by similar parity considerations we can arrange these two types of vectors to sum either both choices of $(0, \pm 1)$ or both choices of $(\pm 1, 0)$. Assume wlog that the $x$-coordinate of both remaining vectors is positive. If the $y$-coordinate of both has the same sign then WLOG assume that it's positive. Notice then that the difference of these vectors lies on some point in the segment from $(-1, 1)$ to $(1, -1)$. If it lies in the segment from $(-1, 1)$ to $(0, 0)$ then we may add either $(1, 0)$ or $(0, -1)$. Otherwise add either $(-1, 0)$ or $(0, 1)$. Finally consider the case where the $y$-coordinate of $v_1$ is positive while that of $v_2$ is negative. Then we may easily see that $v_1 + v_2$ lies on a region congruent to the desired region, shifted one unit to the right, while $v_1 - v_2$ lies on a region congruent to the desired region, shifted one unit up. As we may add either $(-1, 0)$ or $(0, -1)$ to either of these regions, we are finally done.

All odd integers $n\ge 3$ only. For $n$ even, take $a_1=1, a_i=0, b_1=0, b_i=1$ for all $2\le i\le n$. Then $\displaystyle \sum^{n}_{k=1}{x_ka_k}$, $\displaystyle \sum^{n}_{k=1}{x_kb_k}$ are both odd integers, so sum of their absolute value is at least $2$. So $n$ must be odd. For $n$ odd, first observe we may assume $a_i\ge 0$ for all $i$, otherwise we replace $x_i, b_i$ by $-x_i, -b_i$, then the given condition and desired quantity does not change. Also observe that we may assume at least $\lceil \frac{n}{2} \rceil$ of the $b_i$'s are nonnegative, otherwise replace all $b_i$ with $-b_i$ also does not change the given condition and desired quantity. Call this final modification $(*)$. We prove all $n$ odd works by induction. For base case $n=3$, by $(*)$ we may take $a_1,a_2,a_3\ge 0$ and at least $2$ of $b_1,b_2,b_3$ are nonnegative. Consider two cases. \underline{Case I: $b_1,b_2, b_3\ge 0$} Then $b_i=1-a_i$ $\forall 1\le i\le 3$. Consider $a_1\le a_2\le a_3$ and take $x_1=x_3=1, x_2=-1$. Note that $$0\le a_1\le a_1-a_2+a_3\le a_3\le 1$$and $$b_1-b_2+b_3=(1-a_1)-(1-a_2)+(1-a_3)=1-(a_1-a_2+a_3)$$So $0\le b_1-b_2+b_3\le 1$ as well, so $$|a_1-a_2+a_3|+|b_1-b_2+b_3|=(a_1-a_2+a_3)+1-(a_1-a_2+a_3)=1$$ \underline{Case II: $b_1,b_2\ge 0, b_3<0$} Then $b_i=1-a_i$ $\forall 1\le i \le 2$ and $b_3=a_3-1$. Consider $a_1\le a_2$ and take $x_1=x_3=-1, x_2=1$. Let $0\le k=a_2-a_1\le 1$, then note that $$b_2-b_1=(1-a_2)-(1-a_1)=a_1-a_2=-k$$Then $$|a_2-a_1-a_3|+|b_2-b_1-b_3|=|k-a_3|+|-k-b_3|=|k-a_3|+|k+b_3|$$If $k-a_3, k+b_3$ have same sign, then since $0\le k\le 1$, $$|k-a_3|+|k+b_3|=|2k-a_3+b_3|=|2k-1|\le 1$$Else $k-a_3,-k-b_3$ have same sign, then since $0\le a_3\le 1$, $$|k-a_3|+|-k-b_3|=|-a_3-b_3|=|1-2a_3|\le 1$$ This proves the base case. Suppose now for $n=2k-1$, $k\ge 2$ we can always find such $x_1, x_2, \cdots x_n$ satisfying the condition. For $n=2k+1$, by $(*)$ we may find $k+1\ge 3$ pairs of $(a_i,b_i)$ that have both positive. Choose any $3$ such pairs, WLOG let it be $0\le a_1\le a_2\le a_3$ and $b_1,b_2,b_3\ge 0$, then we may apply Case I for $n=3$. So if we define $a'=a_1-a_2+a_3$ and $b'=b_1-b_2+b_3$, then $|a'|+|b'|=1$, so we may apply inductive hypothesis to $a', a_4, \cdots,a_n$, and $b', b_4, \cdots, b_n$ and conclude that we can find $x', x_4, \cdots x_n \in \{1, -1\}$ so that $$\Bigg\vert x'a'+\sum^n_{k=4}{x_ka_k}\Bigg\vert+ \Bigg\vert x'b'+ \sum^n_{k=4}{x_kb_k}\Bigg\vert\le 1$$$$\Bigg\vert x'(a_1-a_2+a_3)+\sum^n_{k=4}{x_ka_k}\Bigg\vert+ \Bigg\vert x'(b_1-b_2+b_3)+ \sum^n_{k=4}{x_kb_k}\Bigg\vert\le 1 $$So we can take $x', -x', x', x_4, \cdots x_n$, which completes the inductive step. So the answer is $n\ge 3$, $n$ odd. Q.E.D

I have a 1-D geometry flavor in my solution. There are a lot of minute details that I gloss over, so follow along with paper and pencil to understand the solution more easily. The answer is all odd $n$. To show that $n$ even does not work, just consider the counterexample $a_1 = 1, a_2 = a_3 = \cdots = a_n = 0$. To show that $n$ odd works, we consider the pairs $(a_1, b_1), ..., (a_n, b_n)$. If both elements in a pair $(a_i, b_i)$ have the same sign or if zero is in that pair, assign $|a_i|$ to the set $R$. Otherwise, assign $|a_i|$ to the set $B$. We are left with $R$ having $0 \le k \le n$ elements, while $B$ has $n - k$ elements. Now order the elements in both $R$ and $B$ from smallest to largest so that we have $R = \{c_1, c_2, ..., c_k\}$ and $B = \{d_1, d_2, ..., d_{n-k}\}$ where $c_1 \le c_2 \le \cdots \le c_n$ and $d_1 \le d_2 \le \cdots \le d_{n-k}$ (if two elements in $R$ or $B$ are the same, just order them in any way). Now assign $\varepsilon_1, \varepsilon_2, ..., \varepsilon_n$ so that $$\sum_{i=1}^n \varepsilon_i a_i = \sum_{i=1}^k (-1)^{i+1}c_i + \sum_{i=1}^{n-k} (-1)^{i+1}d_i.$$Clearly such an assignment is possible. Then $$\sum_{i=1}^n \varepsilon_i b_i = \gamma - \sum_{i=1}^k (-1)^{i+1}c_i + \sum_{i=1}^{n-k} (-1)^{i+1}d_i$$with $\gamma$ being $-1$ if $k$ is even and $1$ if $k$ is odd. Now let $C = \sum_{i=1}^k (-1)^{i+1}c_i$ and let $D = \sum_{i=1}^{n-k} (-1)^{i+1}d_i$. Lemma: Of $C$ and $D$, one is not negative and the other is not positive, and both have absolute value at most $1$. Proof: Let $0 \le x_1 \le x_2 \le \cdots \le x_m \le 1$ be real numbers. If $m$ is even, then $\sum_{i=1}^m (-1)^{i+1}x_i = -\sum_{i=1}^\frac{m}{2}(x_{2i} - x_{2i-1})$. This is just $-1$ times the sum of the distances from $x_i$ to $x_{i+1}$ on the real line for odd $i$, so this quantity is not positive. But then, the distances from $x_i$ to $x_{i+1}$ on the real line for even $i$ are absent from this sum. Thus, this sum must be at most the distance from $x_1$ to $x_m$, which is at most $1$. If $m$ is odd, then $\sum_{i=1}^m (-1)^{i+1}x_i = x_m -\sum_{i=1}^\frac{m-1}{2}(x_{2i} - x_{2i-1})$. This is $x_m$ minus the sum of the distances from $x_i$ to $x_{i+1}$ on the real line for odd $i$. Arguing similarly, we have that this sum is at most the distance from $x_1$ to $x_{m-1}$ which is between $0$ and $x_m$ inclusive. So $\sum_{i=1}^m (-1)^{i+1}x_i$ is nonnegative for $m$ odd and cannot exceed $1$. And since $n$ is odd, $k$ and $n-k$ must have different parities. The result follows. Focusing back on the problem, call the sum given in the problem $S$. Our final task is to show that $S \le 1$ given our assignment of $\varepsilon$'s. If $k$ is even, we have that $S = |C + D| + |-1 - C + D|$. If $C + D$ and $-1 - C + D$ have the same sign, $S = |-1 + 2D|$. By the Lemma, $0 \le D \le 1$ so $S$ is at most $1$. If they have opposite signs, $S =|-1 - 2C|$. By the Lemma, $-1 \le C \le 0$ so again $S$ is at most $1$. If $k$ is odd, we have that $S = |C + D| + |1 - C + D|$. If $C + D$ and $1 - C + D$ have the same sign, $S = |1 + 2D|$. By the Lemma, $-1 \le D \le 0$ so $S$ is at most $1$. If they have different signs, $S = |1 - 2C|$. By the Lemma, $0 \le C \le 1$ so $S$ is at most $1$. The problem is solved.

If $n$ is even, take $(1,0),(0,1),(0,1),\ldots,(0,1)$. It is easy to see that each term on the LHS is an odd positive integer, so the whole sum is at least $2$. Therefore, $n$ even fails. Now, assume $n$ is odd. By swapping signs of $(a_i,b_i)$, we can assume WLOG that $a_i\ge 0$ for all $i$, and that the number of $b_i\ge 0$ is even. Also, WLOG assume $a_1\le\cdots\le a_m$ and $a_{m+1}\ge \cdots\ge a_n$. With this indexing, we claim that \[S:=|-a_1+a_2-a_3+a_4-\cdots-a_{n-2}+a_{n-1}-a_n|+|-b_1+b_2-b_3+b_4-\cdots-b_{n-2}+b_{n-1}-b_n|\le 1.\]Let \[x=(a_2-a_1)+(a_4-a_3)+\cdots+(a_m-a_{m-1}),\]\[y=(a_{m+1}-a_{m+2})+(a_{m+3}-a_{m+4})+\cdots+(a_{n-2}-a_{n-1}),\]and $a=a_n$. We see that $0\le y\le a_{m+1}-a_{n-1}$, and thus, $0\le a+y=a_{m+1}-a_{n-1}+a_n\le 1$. Now, \[S=|a+y-x|+|a+y+x-1|.\]If $a+y-x$ and $a+y+x-1$ have the same sign, then $S=|2(a+y)-1|$, and $S=|2x-1|$ if they have opposite signs. But $0\le a+y,x\le 1$, so $S\le 1$, as desired. $\blacksquare$ Remark See v_Enhance's geometric solution for motivation.

Its trivial that even $n$ does not works.If we think the pair $(a_i,b_i)$ is a vector than the condicion of the problem means that the some of one vector from $O$ to an arbitrary point of the unit square with even number of vectors on the boundary of this square is a vector, which lies in the unit square.But it is obvious.

v_Enhance wrote: The answer is all odd $n$. First Solution (mine): For even $n \ge 2$, one can conjure the following counterexample: set $a_1 = a_2 = \dots = a_{n-1} = 1$ and $a_n = 0$ (and $b_1 = \dots = b_{n-1} = 0$ and $b_n = 1$). In that case both terms of the inequality are odd integers, hence they have sum at least $2$. Now we prove odd positive integers are always possible. We will make the following simplifications: By negating $\{a_i, b_i\}$ in pairs, we may assume $a_i \ge 0$ for all $i$. By negating all $b_i$ at once, we may assume there are an odd number of positive $b_i$'s. Assume $a_1 < \dots < a_k$ correspond to positive $b_i$'s and $a_{k+1} < \dots < a_n$ correspond to negative $b_i$'s. We claim that we can take $\varepsilon_1 = +1$, $\varepsilon_2 = -1$, \dots, $\varepsilon_k = +1$ and $\varepsilon_{k+1} = +1$, $\varepsilon_{k+2} = -1$, \dots, $\varepsilon_n = -1$. Here is an example: \[ \begin{array}{c|rrrrr|rr} \varepsilon_i & +1 & -1 & +1 & -1 & +1 & +1 & -1 \\ \hline a_i & 0.1 & 0.2 & 0.4 & 0.6 & 0.8 & 0.3 & 0.6 \\ b_i & 0.9 & 0.8 & 0.6 & 0.4 & 0.2 & -0.7 & -0.4 \end{array} \]If one takes the four sums in the quadrant above, we in fact get four numbers as follows: \[ \begin{array}{r|r} \alpha & -\gamma \\ \hline \beta & -\gamma \end{array} \]where $\alpha+\beta=1$ and all three numbers are in $[0,1]$. Second Solution (geometric, outline): We just prove that odd $n$ work. As before assume $a_i > 0$, with an odd number of positive $b_i$'s and an even number of negative $b_i$'s. View the points as vectors in ${\mathbb R}^2$ lying on a ``tilted square''. Alternate signs on each vector now, along the boundary of the square. It's then not difficult to check that sum of the red arrows lies inside the square. [asy][asy]size(8cm); pair A = dir(90); pair B = dir(0); pair C = dir(-90); pair D = dir(180); draw(A--B--C--D--cycle, blue); draw(A--C, blue); draw(B--D, blue); pair P_1 = 0.3*B+0.7*A; pair P_2 = 0.5*B+0.5*A; pair P_3 = 0.8*B+0.2*A; pair P_4 = 0.9*B-0.1*A; pair P_5 = 0.7*B-0.3*A; pair P_6 = 0.45*B-0.55*A; pair P_7 = 0.15*B-0.85*A; pair O = origin; pen r = red + 1.2; draw( O--P_1, r, EndArrow(TeXHead)); draw(P_2--P_3, r, EndArrow(TeXHead)); draw(P_4--P_5, r, EndArrow(TeXHead)); draw(P_6--P_7, r, EndArrow(TeXHead)); label("$(0,1)$", A, A); label("$(1,0)$", B, B); label("$(0,-1)$", C, C); label("$(-1,0)$", D, D); dot(A); dot(B); dot(C); dot(D); dot("$P_1$", P_1, dir(45)); dot("$P_2$", P_2, dir(45)); dot("$P_3$", P_3, dir(45)); dot("$P_4$", P_4, dir(300)); dot("$P_5$", P_5, dir(300)); dot("$P_6$", P_6, dir(300)); dot("$P_7$", P_7, dir(300)); dot(O);[/asy][/asy] Can I ask your motivation on proving the statement for odd?

We claim it is only possible for odd $n$. For even $n$, take $a_1=\cdots=a_{n-1}=1$ and $a_n=1$, and $b_1=\cdots=b_{n-1}=0$ and $b_n=1$. Then the second term on the LHS is 1, while the first is at least 1 since $n-1$ is odd. Hence, the LHS is at least 2, contradiction. Now we will show that odd $n$ work. Lemma: Given reals $x_1,\ldots,x_n \in [0,1]$, there exist $\varepsilon_1,\ldots,\varepsilon_n \in \{-1,1\}$ such that \[ 0\le \varepsilon_1x_1+ \cdots + \varepsilon_nx_n \le 1. \]Proof: Simply order WLOG $x_1\le \cdots \le x_n$, and choose $\varepsilon_i=(-1)^i$. $\square$ Now, WLOG assume that all the $a_i$'s are positive; this is because we can switch the sign of both $a_i$ and $b_i$ at once by changing the sign of $\varepsilon_i$. Furthermore, WLOG permute the $b_i$'s such that we first have the positive $b_i$'s in increasing order, and then we have the negative $b_i$'s in decreasing order. Note that this also permutes the $a_i$'s. An example is \[ \begin{array}{c c c c c } \vec{a} = (0.4 & 0.1 & 0.7 & 0.5 & 0.3) \\ \vec{b} = (0.6 & 0.9 & 0.3 & -0.5 & -0.7) \end{array} \]Furthermore, we can WLOG assume that there are an even number of negative $b_i$'s; if not, switch the positives and negatives. Suppose there are $k$ positive $b_i$'s. Then, \begin{align*} \varepsilon_1a_1+\cdots+\varepsilon_na_n &= [a_1-a_2+\cdots - a_k] + [a_{k+1} - a_{k+2} + \cdots - a_n] \\ &= M + N \end{align*}where $0\le M\le 1$ and $-1\le N\le 0$ by the lemma. Hence $|M+N|\le 1$, as desired. And \begin{align*} \varepsilon_1b_1+\cdots+\varepsilon_nb_n &= (1-a_1)-(1-a_2)+\cdots-(1-a_k) + (a_{k+1}-1) - (a_{k+2}-1) + \cdots - (a_n-1) \\ &= [1-a_1 + a_2 - \cdots + a_k] + [a_{k+1} - a_{k+2} + \cdots -a_n] \\ &= (1-M) + N. \end{align*}Similarly, $|(1-M) + N|\le 1$, as desired.

Amazing problem. We reinterpret the problem as follows: We have a set of vectors whose head is on the square $|x|+|y|=1$ and whose tail is the origin, and we want to find all $n$ such that it is possible to always add/subtract vectors out of the $n$ vectors such that the resulting vector is in the square. [asy][asy] draw((-1,0)--(0,1)--(1,0)--(0,-1)--cycle); draw((0.7,0.3)--(0,0)--(-0.5,0.5),purple); dot((0,0)); [/asy][/asy] We claim the answer is all odd $n$. Note that $1$ copy of $<0,1>$ and $2m-1$ copies of $<0,1>$ will fail because $|1|+|1|=2>1,$ so even $n$ are out of the question. Now for odd $n,$ we use an alternating sum argument. The problem still holds if we force every vector to have a positive $y$ component since subtraction is legal. Alternate the sum based on $x$ component, as shown in the diagram below. (Green vectors add, red vectors subtract.) [asy][asy] draw((-1,0)--(0,1)--(1,0)--(0,-1)--cycle); draw((0.7,0.3)--(0,0)--(-0.5,0.5),green); draw((-0.1,0.9)--(0,0),red); dot((0,0)); [/asy][/asy] Note the sum is equivalent to the sum of the blue vectors. [asy][asy] draw((-1,0)--(0,1)--(1,0)--(0,-1)--cycle); draw((0.7,0.3)--(0,0),green); draw((-0.5,0.5)--(0,0),blue); draw((-0.1,0.9)--(0,0),red); dot((0,0)); draw((-0.1,0.9)--(0.7,0.3),blue); [/asy][/asy] But also note that this blue sum is equivalent to the following. [asy][asy] draw((-1,0)--(0,1)--(1,0)--(0,-1)--cycle); draw((0.7,0.3)--(0,0)--(-0.5,0.5),green); draw((-0.1,0.9)--(0,0),red); dot((0,0)); draw((-0.1,0.9)--(0,1)--(0.7,0.3),blue); draw((0,0)--(-1,0)--(-0.5,0.5),blue); [/asy][/asy] Note that the linear combinations of $<1,1>$ and $<-1,0>$ when starting from the left vertex will span the square, so we are done.

We claim the answer is all odd $n$. We first show that even $n$ fail. Let $(a_1, b_1) = (1, 0)$, and $(a_i, b_i) = (0, 1)$ for all $i > 1$. In this case, no matter the assignment of signs, $\left|\sum_{i = 1}^n \varepsilon_i a_i\right|$ and $\left|\sum_{i = 1}^n \varepsilon_i b_i\right|$ will be odd positive integers, hence their sum will be at least $2$, showing the failure. We now prove that all odd $n$ work; note trivially that $n = 1$ works. We make a few assumptions. WLOG assume all $a_i$ are positive (i.e., if $a_i < 0$, flip the signs of $a_i$, $b_i$, and $\varepsilon_i$). Additionally, suppose the number of negative $b_i$ is either $0$ or odd: if all $b_i$ are negative, or a positive, even number of $b_i$ are negative, flip the signs of every $b_i$ (which doesn't affect the sum). We now solve the $n = 3$ case, which allow us to complete an induction. Note by our assumptions that there are either $0$ or $1$ negative $b_i$. Case 1: If all $b_i$ are positive, we can assign $\varepsilon_i$ to attain a sum of $1$. Proof of Case 1: Suppose $1 > a_1 > a_2 > a_3 > 0$, and note $b_1 = 1 - a_1, b_2 = 1 - a_2, b_3 = 1 - a_3$. Put $\varepsilon_1 = 1, \varepsilon_2 = -1, \varepsilon_3 = 1$. Then, $0 < a_1 - a_2 + a_3 < 1$, so that $0 < b_1 - b_2 + b_3 = 1 - (a_1 - a_2 + a_3) < 1$ as well. As such, the desired sum is $1$, and the lemma is proven. $\blacksquare$ Case 2: If $1$ of the $b_i$ is negative, we can ensure the sum is at most $1$. Proof of Case 2: Suppose $b_1 = a_1 - 1$ is negative, and that $a_2 > a_3$. Assign $\varepsilon_1 = 1, \varepsilon_2 = -1, \varepsilon_3 = 1$. Then $b_1 - b_2 + b_3 = a_1 + a_2 - a_3 - 1$. We have \begin{align*} \left|\sum_{i = 1}^3 \varepsilon_ia_i\right| + \left|\sum_{i = 1}^3 \varepsilon_ib_i\right| &= \max(|(a_1 - a_2 + a_3) + (a_1 + a_2 - a_3 - 1)|, |(a_1 - a_2 + a_3) - (a_1 + a_2 - a_3 - 1)|) \\ &= \max(|2a_1 - 1|, |1 - 2(a_2 - a_3)|) \\ &\leq 1, \end{align*}solving this case as well. $\blacksquare$ These two cases solve the $n = 3$ case. We now induct to show that all larger odd numbers work as well. Note that $n \geq 5$, which implies that at least $3$ of the $b_i$ have the same sign. Suppose (by flipping all $b_i$ if necessary) that $b_1, b_2, b_3$ are all positive. Applying case $1$, there is a way to assign $\varepsilon_1, \varepsilon_2, \varepsilon_3$ so that $|\sum_{i = 1}^3 \varepsilon_ia_i| + |\sum_{i = 1}^3 \varepsilon_ib_i| = 1$. By deleting $a_2$ and $a_3$ and replacing $(a_1, b_1)$ with $(\sum_{i = 1}^3 \varepsilon_ia_i, \sum_{i = 1}^3 \varepsilon_ib_i)$, we may induct down. Done! $\Box$

Our answer is all odd $n$. For even $n$, we can just have one pair $(a_i, b_i) = (0, 1)$ and the remaining $n-1$ pairs be $(1, 0)$. This way, since parity is preserved under addition and subtraction,\[\sum_{i = 1}^n \varepsilon_i a_i \equiv 0 + (n-1) \equiv 1 \pmod 2 \text{ and } \sum_{i = 1}^n \varepsilon_i b_i \equiv 1 \pmod 2\]hence both absolute value summands are odd hence the sum is at least $2$. Next, we will find such $\varepsilon_i$ for odd $n$. Note that WLOG we may assume $a_i \in [0, 1]$ since if they are negative we can adjust $\varepsilon_i$ to switch the signs and nothing will be affected. Suppose we order the terms so that $a_1 \leq \ldots \leq a_k$ are the $a_i$ terms for which $b_i$ are positive and $a_{k+1} \leq \ldots \leq a_n$ are the $a_j$ terms for which $b_j$ are nonpositive. WLOG $k$ is even else we can negate every term. Choose the $\varepsilon_i$'s so that\[\{\varepsilon_1 = 1, \varepsilon_2 = -1, \ldots , \varepsilon_k = -1\} \text{ }\cap \text{ }\{\varepsilon_{k+1} = 1, \varepsilon_{k+2} = -1, \ldots , \varepsilon_{n} = 1\}.\]Let $S = \varepsilon_1a_1 + \ldots + \varepsilon_ka_k$ and $T = \varepsilon_{k+1}a_{k+1} + \ldots + \varepsilon_na_n$. Note that\[ \left| \sum_{i=1}^n \varepsilon_i a_i \right| = |S + T| \text{ and } \left|\sum_{i=1}^n \varepsilon_i b_i \right| = |1 - S + T|\]and that\[|S + T| + |1 + S - T| \leq 1\]since clearly $S \in [0, -1]$ and $T \in [0, 1]$. $\blacksquare$

The answer is all odd $n.$ Claim: All even $n$ fail. Proof. Consider $(1,0)$ and $n-1$ pairs of $(0,1).$ $\blacksquare$ Claim: All odd $n$ work. Proof. WLOG assume all $0\le a_1\le a_2\le \dots \le a_n$ and $b_1, b_2, \dots,b_k < 0 $ and $0\le b_{k+1} , b_{k+2},\dots ,b_n$ for even $k$ by flipping signs of $\varepsilon_i.$ Set $\varepsilon_i = -1$ for $i$ even and $1$ for $i$ odd. Define $x$ such that, $$-1 \le \min_{1\le i \le k} b_i \le \sum_{i=1}^k (-1)^{i+1} b_i = -x \le 0 \implies \sum_{i=1}^k (-1)^{i+1} a_i = \sum_{i=1}^k (-1)^{i+1} (1+b_i) = -x.$$Similarly, define $y$ such that, $$0\le \min_{k+1 \le i \le n} b_i \le \sum_{i=k+1}^n (-1)^{i+1} b_i = y \le \max_{k+1\le i\le n} b_i \le 1 \implies \sum_{i=k+1}^n (-1)^{i+1} a_i = \sum_{i=k+1}^n (-1)^{i+1} (1-b_i) = 1-y.$$Hence, $$ \left| \sum_{i=1}^n \varepsilon_i a_i \right| + \left| \sum_{i=1}^n \varepsilon_i b_i \right| = |1-x - y| + |y-x|,$$Which, since $0\le x,y \le 1,$ $|1-x-y| + |y-x| \le 1.$ $\blacksquare$

The answer is all odd $n.$ As a counterexample for even $n$ take $$a_1=a_2=\dots=a_{n-1}=b_n=1$$$$b_1=b_2=\dots=b_{n-1}=a_n=0.$$Then both $\left| \sum_{i=1}^n \varepsilon_i a_i \right|, \left| \sum_{i=1}^n \varepsilon_i b_i \right|$ are nonnegative odd integer, so their sum is at least $2.$ Now we give a construction for case of odd $n.$ Firstly modify sequences of $a_i,b_i$ as follows (it doesn't affect on problem): until $\exists k:a_k<0$ change pair $(a_k,b_k)\rightarrow (-a_k,-b_k);$ if sequence $b_i$ contains even number of nonnegative numbers, then change $(b_1,b_2,\dots,b_n)\rightarrow (-b_1,-b_2,\dots,-b_n).$ Now by rearragment we may assume that $$b_1\leq b_2\leq \dots \leq b_{2m}<0\leq b_{2m+1}\leq b_{2m+2}\leq \dots \leq b_{n}.$$We claim, that $\varepsilon_i=(-1)^{i+1}$ works. Define $0\leq x,y\leq 1$ as $$-x=\sum_{i=1}^{2m} (-1)^{i+1} a_i=\sum_{i=1}^{2m} (-1)^{i+1} (1+b_i),\text{ } y=\sum_{i=2m+1}^{n} (-1)^{i+1} a_i=\sum_{i=2m+1}^{n} (-1)^{i+1} (1-b_i).$$Then $\left| \sum_{i=1}^n \varepsilon_i a_i \right| + \left| \sum_{i=1}^n \varepsilon_i b_i \right| = |y-x|+|1-y-x|\leq 1$ $\blacksquare$

The answer is odds only. If $n$ is even, let $a_1=1$, $a_2,\dots, a_n=0$, then since $\varepsilon_i a_i\in \mathbb Z$, we can write \[\left| \sum_{i=1}^n \varepsilon_i a_i \right| \equiv \left | \sum_{i=1}^n a_i \right |\equiv 1\pmod 2\]and similarly for $b_i$. Thus, since both are odd, both must be at least one, contradiction. To prove that it is true for odds: consider the square $|x|+|y|=1$. We have an odd number of vectors from the origin to a point on this square. Since we can subtract, we might as well make all $y$ coordinates positive. Let the vectors' endpoints be $A_1$, $A_2$, $\dots$, $A_n$. Note that \[\overrightarrow{A_1}+\overrightarrow{A_2A_3}+\overrightarrow{A_4A_5}+\overrightarrow{A_{n-1}A_n}\]will trace out some of the squares top two sides, so the result will be in the square. We are done.

Got a hint for vector-like approach Note that for even n, when $a_1=1,a_2,...,a_n=0$ and similarly for the sequence of b, we deduce both of them are 1 mod 2; since they're positive, they're at least 1+1=2. Then, for odd n, look at the square |x|+|y|=1, with for convenience assuming all a are >0, while odd number of b's are positive and even number of b's are negative; this is well motivated because we want to show it stays inside the square, and difference of vectors are easy to control. Indeed, note that $0->P_1$ (where it's gotten from vector $a_1$ and $b_1$ representing the x and y coordinates of the vector in that direction), then $P_2$->$P_3$ (from $a_2$ adding to $a_3$ and subtracting $b_2$ from $b_3$ from the way we picked the signs) etc. until $P_{n-1}$ to $P_n$. Since each of those vectors from $P_k$->$P_{k+1}$ stay on the square (when the initial $0$->$P_1$ is on the square, and the difference of those two vectors 0->$P_k$ from the vector going 0->$P_{k+1}$ is just the vector taking $P_2$ to $P_3$), we're done.

Claim: Even $n$ doesn't work. Proof. Take $(a_1,b_1)=(1,0)$, $(a_2,b_2)=(a_3,b_3)=\dots=(a_{2k},b_{2k})=(0,1)$. Since $$|e_1|+|e_2+\dots+e_{2k}|>|e_1|=1,$$the claim follows. //// Now, suppose that $n=2k-1$. We can assume WLOG that $a_i$ and $b_i$ are non-negative (edit: hmm, it looks like we can't assume $b_i\geq 0$ without losing generality oops. anyway fixing it isn't that hard, luckily) and that $$1\geq a_1\geq a_2\geq \dots \geq a_{2k-1}\geq 0.$$Take $e_i=(-1)^{i-1}$ for $1\leq i\leq 2k-1$. Note that $$1\geq a_1\geq \sum_i (-1)^{i-1}a_i \geq a_{2k-1}\geq 0.$$It follows that $$\left |\sum_i (-1)^{i-1}a_i \right|+\left |\sum_i (-1)^{i-1}b_i \right|=\left |\sum_i (-1)^{i-1}a_i \right|+\left |1-\sum_i (-1)^{i-1}a_i \right|=1,$$as required.