Question 97
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}$.
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}$.