Convex sets: a hint on how to solve a problem

Question

Could anyone give me a hint on how to solve the following problem?

Let $X_1, \dots, X_{d+1}$ be some finite sets in $\mathbb{R}^d$, such that the origin lies in ${\rm conv}(X_i)$ for all $i \in \{1, 2, \dots, d+1\}$. The problem is to prove that there exist points $x_i \in X_i$, $i \in \{1, 2, \dots, d+1\}$, such that the origin lies in ${\rm conv}(\{x_1,x_2,\dots,x_{d+1}\})$.

I've tried everything that came to my mind.

Thank you for your help.

Answer 1

The problem can be proved by contradiction and by the use of hyperplane separation theorem.

One can assume that for each $(x_1, \dots, x_{d+1}) \in X_1 \times \cdots \times X_{d+1}$ the ${\rm conv}(\{x_1, \dots, x_{d+1}\})$ doesn't contain the origin. Let $C$ be the colset one to the origin. Then by separation theorem there exists a hyperplane such that the origin is on one side and $C$ on the other. Since ${\rm conv}(X_1)$ contains the origin there also has to be $a \in X_1$ such that $a$ is on the same side as the origin. Consider $C' = {\rm conv}(a, x_2, \dots x_{d+1})$. It is easy to see that $C'$ is closer to the origin than $C$, which yields a contradiction.

Answer 2

I do not believe it is true. Indeed, take $X_1 = \{(-1,0) ; (1,0)\}$ and $X_2 = \{(0,-1) ; (0,1)\}$. The origin lies in $\text{conv}(X_i)$ for all $i$ but there does not exist $(x_1,x_2)\in X_1 \times X_2$ such that $0\in \text{conv}(x_1,x_2)$.