Past exam of the computer science course of the University of Oxford / 2015 / Computational learning theory / 1 / c / Solution

Choose distinct points $x_1,\dots ,x_{d+2}$ of $S$. The $d+2$ vectors $(x_i,1)$ lie in the $(d+1)$-dimensional vector space ${\mathbb{R}}^{d+1}$, so they are linearly dependent. Hence there are real numbers ${\lambda }_i$, not all zero, such thatThe second equality forces both a positive and a negative coefficient. Put $I_{+}=\{i:{\lambda }_i>0\}$, $I_{-}=\{i:{\lambda }_i<0\}$, andRearranging the first equality givesEach side is a convex combination: the coefficients are positive and sum to one. Thus $z$ belongs to both convex hulls. Place the points with indices in $I_{+}$ in $A$, those with indices in $I_{-}$ in $B$, and assign every zero-coefficient point and every remaining point of $S$ to $A$. Then $A,B$ are nonempty, disjoint, and have union $S$. Adding points cannot shrink a convex hull, soThis proves the intersecting convex hull partition theorem, including when $S$ has more than $d+2$ points or is infinite: only the initial finite collection was needed.