HMIC, 2018

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Consider a finite set of points $T \in \mathbb{R}^n$ contained in the $n$ -dimensional unit ball centered at the origin, and let $X$ be the convex hull of $T$ . Prove that for all positive integers $k$ and all points $x \in X$ , there exist points $t_1, t_2, \ldots, t_k \in T$ , not necessarily distinct, such that their centroid
$\frac{t_1 + t_2 + \cdots + t_k}{k}$
has Euclidean distance at most $\frac{1}{\sqrt{k}}$ from $x$ .

(The $n$ -dimensional unit ball centered at the origin is the set of points in $\mathbb{R}^n$ with Euclidean distance at most 1 from the origin. The convex hull of a set of points $T \in \mathbb{R}^n$ is the smallest set of points $X$ containing $T$ such that each line segment between two points in $X$ lies completely inside $X$ .)

Solution

Solution:

By the definition of convex hull, we can write $x=\sum_{i=1}^{m} \lambda_{i} z_{i}$ , where each $z_{i} \in T$ , each $\lambda_{i} \geq 0$ and $\sum_{i=1}^{m} \lambda_{i}=1$ . Consider then a random variable $Z$ that takes on value $z_{i}$ with probability $\lambda_{i}$ . We have $\mathbb{E}[Z]=x$ . Let $\bar{Z}=\frac{1}{k} \sum_{i=1}^{k} Z_{i}$ , where each $Z_{i}$ is an independent copy of $Z$ . Then we wish to compute
$\operatorname{Var}[\bar{Z}]=\frac{1}{k^{2}} \sum_{i=1}^{k} \operatorname{Var}\left[Z_{i}\right]$
Finally, we have
$\operatorname{Var}\left[Z_{i}\right]=\mathbb{E}\left[\left\|Z_{i}-x\right\|^{2}\right]=\mathbb{E}\left[\left\|Z_{i}\right\|^{2}\right]-x^{2} \leq \mathbb{E}\left[\left\|Z_{i}\right\|^{2}\right] \leq 1$
The second equality follows from the identity $\operatorname{Var}[X]=\mathbb{E}\left[X^{2}\right]-\mathbb{E}[X]^{2}$ . Now, we know that
$\mathbb{E}\left[\left\|x-\frac{1}{k} \sum_{i=1}^{k} Z_{i}\right\|^{2}\right]=\operatorname{Var}[\bar{Z}] \leq \frac{1}{k}$
Thus, there must exist some realization of $x_{i}$ of the $Z_{i}$ such that
$\left\|x-\frac{1}{k} \sum_{i=1}^{k} x_{i}\right\|^{2} \leq \frac{1}{k}$
and we are done.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.