HMIC

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:

Let $v_{1}, v_{2}, \ldots, v_{m}$ be vectors in $\mathbb{R}^{n}$ , such that each has a strictly positive first coordinate. Consider the following process. Start with the zero vector $w=(0,0, \ldots, 0) \in \mathbb{R}^{n}$ . Every round, choose an $i$ such that $1 \leq i \leq m$ and $w \cdot v_{i} \leq 0$ , and then replace $w$ with $w+v_{i}$ .
Show that there exists a constant $C$ such that regardless of your choice of $i$ at each step, the process is guaranteed to terminate in $C$ rounds. The constant $C$ may depend on the vectors $v_{1}, \ldots, v_{m}$ .

Solution

Solution:

Let $w_{0}=0$ , let $w_{r}$ be the vector $w$ after $r$ rounds. Also, let $e_{1}$ denote the vector $(1,0, \ldots, 0)$ . Note that
$w_{r+1}^{2}=\left(w_{r}+v_{i}\right)^{2}=w_{r}^{2}+v_{i}^{2}+2 w_{r} \cdot v_{i} \leq w_{r}^{2}+v_{i}^{2}$
as we have by the condition that $w_{r} \cdot v_{i} \leq 0$ . Therefore, we have by induction that $\left|w_{r}\right| \leq M \sqrt{r}$ , where $M=\max _{i}\left|v_{i}\right|$ . Also, we have that
$w_{r+1} \cdot e_{1}=w_{r} \cdot e_{1}+v_{i} \cdot e_{1}$
so $w_{r} \cdot e_{1} \geq m r$ , where $m=\min _{i}\left(v_{i} \cdot e_{1}\right)>0$ .
Now using the obvious inequality
$M \sqrt{r} \geq\left|w_{r}\right| \geq w_{r} \cdot e_{1} \geq m r$
we get that $r \leq \frac{M^{2}}{m^{2}}$ , as desired.

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.