Convex combination of $2^n$ vectors from cartesian products of half-spaces

Question

The following sets in $\mathbb{R}^2$ are defined: $$ H_1 :=\left\{x\in\mathbb{R}^2\ \vert\ x_1\geq0\right\}\\ H_2 :=\left\{x\in\mathbb{R}^2\ \vert\ x_2\geq0\right\}\\ E_1 :=\left\{x\in\mathbb{R}^2\ \vert\ x_1=0\right\}\\ E_2 :=\left\{x\in\mathbb{R}^2\ \vert\ x_2=0\right\}\\ H_{12} :=\left\{x\in\mathbb{R}^2\ \vert\ x_1,x_2\geq0\right\} $$ Let $n\in\mathbb{N}$. Let there be a given vector $\lambda_i\in\mathbb{R}^{2n}$ from each of the $2^n$ different n-fold cartesian products of $H_1$ and $H_2$: $$ \lambda_1 \in H_1\times H_1\times H_1\times\dots\times H_1\\ \lambda_2 \in H_2\times H_1\times H_1\times\dots\times H_1\\ \lambda_3 \in H_1\times H_2\times H_1\times\dots\times H_1\\ \lambda_4 \in H_2\times H_2\times H_1\times\dots\times H_1\\ \vdots\\ \lambda_{2^n} \in H_2\times H_2\times H_2\times\dots\times H_2 $$ Claim: There exists a $\lambda\in conv(\lambda_1, \dots, \lambda)$ with $$ \lambda\in\left(E_1\cup E_2\cup H_{12}\right)\times\dots\times\left(E_1\cup E_2\cup H_{12}\right). $$ Proof idea:
Using the hyperplane separation theorem one gets a vector $\varphi_j\in\mathbb{R}^{2n}$ from each of the $3^n$ different n-fold cartesian products of $E_1$, $E_2$ and $H_{12}$: $$ \varphi_1\in E_1\times E_1\times E_1\times\dots\times E_1\\ \varphi_2\in E_2\times E_1\times E_1\times\dots\times E_1\\ \varphi_3\in H_{12}\times E_1\times E_1\times\dots\times E_1\\ \varphi_4\in E_1\times E_2\times E_1\times\dots\times E_1\\ \varphi_5\in E_2\times E_2\times E_1\times\dots\times E_1\\ \varphi_6\in H_{12}\times E_2\times E_1\times\dots\times E_1\\ \vdots\\ \varphi_{3^n}\in H_{12}\times H_{12}\times H_{12}\times\dots\times H_{12} $$ If there is a vector $\lambda\in conv(\lambda_1, \dots, \lambda)$ and a $\varphi_j$ ($j\in\{1,\dots,3^n\}$) with $\varphi_j^\intercal\lambda\geq0$, then the claim follows.

Answer 1

Here is an important "wlog" step. By compactness we can pick $\hat{\lambda_1},\dots,\hat{\lambda_{2^n}}\in\mathrm{conv}(\lambda_1,\dots,\lambda_{2^n})$ satisfying the same conditions about being in Cartesian products of $H_1$ and $H_2,$ but minimizing the volume of the convex hull $\mathrm{conv(\hat{\lambda_1},\dots,\hat\lambda_{2^n}}),$ and then minimizing the number of $i$ such that $\lambda_i$ is an extreme point of this convex hull: if the volumes are the same, we prefer a choice with fewer $\lambda_i$ at vertices. The convex hull of the $\hat{\lambda_i}$ is a subset of the convex hull of the $\lambda_i,$ so we can assume that $\lambda_i=\hat{\lambda_i}.$

One of the $\lambda_i$ is an extreme point of the convex hull of $\lambda_1,\dots,\lambda_{2^n}.$ Let's assume it's $\lambda_1.$ I claim that $\lambda_1\in(E_1\cup H_{12})^n.$ It is enough to show $((\lambda_1)_1,(\lambda_1)_2)\in E_1\cup H_{12}$ because the other co-ordinates can be handled symmetrically. Let $a=((\lambda_1)_1,(\lambda_1)_2)$ and $b=((\lambda_2)_1,(\lambda_2)_2),$ so $a\in H_1$ and $b\in H_2.$ (For handling other co-ordinates we would need to use a different $\lambda_i$ than $\lambda_2.$) Either $a_1=0$ or $a_1>0.$ In the first case we're done: $a\in E_1.$ In the second case there exists $0<\theta<1$ with $a_1\theta+b_1(1-\theta)\geq 0$ (for example $\theta=|b_1|/(a_1+|b_1|)$). Define $\lambda_1'=\lambda_1\theta+\lambda_2(1-\theta).$ Note that $\lambda_1'\in H_1^n,$ and either $\mathrm{conv}(\lambda_1',\lambda_2,\dots,\lambda_{2^n})$ has smaller volume (because $\lambda_1\neq \lambda_i$ for $i\neq 1$), or $\lambda_1'$ is not extreme in this new convex hull. By the minimality assumptions in the previous paragraph we get $\lambda_1=\lambda_1'.$ So $a=b\in H_{12}.$ In either case $a\in E_1\cup H_{12}$ as required.