Vectors and probabilistic method

56 Views Asked by At

I've seen task Probabilistic method proof and I've come up with some questions (problems)

  1. I understand how to solve Probabilistic method proof problem

Now I am interested in the following questions:

  1. Is it true, that this estimate is the best possible? How can I prove that for each natural n there is dimension d and such vectors $$v_1, v_2 ... v_n \in R^d$$ of length 1 such that for each $$a_1,a_2, ...a_n \in \{-1, 1\}$$ it is true that $$||\sum_{i = 1}^{n}{a_iv_i}||\ge \sqrt{n}$$

And the second question is:

  1. Let $$v_1, ... v_n \in R^d, \forall i : ||v_i||=1 \\ \alpha_1,...\alpha_n \in \{-1, 1\} \\ u = \sum_{i=1}^{n}{\alpha_iv_i}$$

prove that it's possible to choose such $$a_1, ... a_n \in \{-1, 1\} \quad that \\ ||\sum_{i = 1}^{n}{a_iv_i} - u|| \le \sqrt{n}$$ and if not all $$\alpha_i$$equal to zero, this inequality can be not strict (meaning that problem in Probabilistic method proof) is the worst case scenario)