Prove that 0 is in the convex hull of points chosen from each orthant

Question

If we arbitrarily choose a point from each orthant in $\mathbb{R}^n$, that is we choose $2^n$ points in total, how do we prove that 0 is in the convex hull of these $2^n$ points? It seems obvious, but when I sit down and start thinking about it, I couldn't definitely find a set of $\lambda_i, i = 1,2,\cdots,2^n$ such that $0 \leq \lambda_i \leq 1, \sum_i \lambda_i = 1$ and $0 = \sum_i \lambda_i x_i$, where $x_i, i = 1,2,\cdots,2^n$ are any set of points satisfying the condition.

Answer 1

Induct on dimension.

In the $n=1$ base case, you have a positive number and a negative number; $0$ can be represented as a convex combination of them.

For $n>1$: Given your $2^n$ points, one from each orthant, divide them into 2 sets of size $2^{n-1}$, where the first set has points whose last coordinates are positive and the second set where the last coordinates are negative. By the inductive hypothesis there is a convex combo of the first set of points such that the first $n-1$ coordinates vanish, and similarly for the second set. The last coordinates of these two convex combos are positive and negative, so there is a convex combo of them that is zero.

Answer 2

Take in pairs the points that differ in sign for the coordinate $n$ (and only that one) and form the convex combinations such that that coordinate is cancelled.

Now you have $2^{n-1}$ points in each orthants of the diminished space.

The results holds because the convex combination of linear combinations is a convex combination.