uniolympiads Ελληνικά

IMC 2013, Day 2, Problem 3

Suppose that v1,…,vdv_1, \dots, v_d are unit vectors in Rd\mathbb{R}^d. Prove that there exists a unit vector uu such that

∣u⋅vi∣≤1/d|u \cdot v_i| \le 1/\sqrt{d}

for i=1,2,…,di = 1, 2, \dots, d. (Here ⋅\cdot denotes the usual scalar product on Rd\mathbb{R}^d.)

Original from the official PDFSuppose that v 1 , . . . , v d are unit vectors in R d . Prove that there exists a unit vector u such that √ |u · v i | ≤ 1/ d for i = 1, 2, . . . , d. (Here · denotes the usual scalar product on R d .)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Tomasz Tkocz, University of Warwick)

Solution. If v1,…,vdv_1, \ldots, v_d are linearly dependent then we can simply take a unit vector uu perpendicular to span⁡(v1,…,vd)\operatorname{span}(v_1, \ldots, v_d). So assume that v1,…,vdv_1, \ldots, v_d are linearly independent. Let w1,…,wdw_1, \ldots, w_d be the dual basis of (v1,…,vd)(v_1, \ldots, v_d), i.e.

wi⋅vj=δij={1if i=j0if i≠jfor 1≤i,j≤d.w_i \cdot v_j = \delta_{ij} = \begin{cases} 1 & \text{if } i = j \\ 0 & \text{if } i \ne j \end{cases} \quad \text{for } 1 \le i, j \le d.
From wi⋅vi=1w_i \cdot v_i = 1 we have ∣wi∣≥1|w_i| \ge 1.

For every sequence ε=(ε1,…,εd)∈{+1,−1}d\varepsilon = (\varepsilon_1, \ldots, \varepsilon_d) \in \{+1,-1\}^d of signs define uε=∑i=1dεiwiu_\varepsilon = \sum_{i=1}^d \varepsilon_i w_i. Then we have

∣uε⋅vk∣=∣∑i=1dεi(wi⋅vk)∣=∣∑i=1dεiδik∣=∣εk∣=1for k=1,…,d.|u_\varepsilon \cdot v_k| = \left|\sum_{i=1}^d \varepsilon_i (w_i \cdot v_k)\right| = \left|\sum_{i=1}^d \varepsilon_i \delta_{ik}\right| = |\varepsilon_k| = 1 \quad \text{for } k = 1, \ldots, d.

Now estimate the average of ∣uε∣2|u_\varepsilon|^2.

12d∑ε∈{+1,−1}n∣uε∣2=12d∑ε∈{+1,−1}n(∑i=1dεiwi)⋅(∑j=1dεjwj)==∑i=1d∑j=1d(wi⋅wj)(12d∑ε∈{+1,−1}nεiεj)=∑i=1d∑j=1d(wi⋅wj)δij=∑i=1d∣wi∣2≥d.\begin{aligned} \frac{1}{2^d}\sum_{\varepsilon\in\{+1,-1\}^n} |u_\varepsilon|^2 &= \frac{1}{2^d}\sum_{\varepsilon\in\{+1,-1\}^n} \left(\sum_{i=1}^d \varepsilon_i w_i\right)\cdot\left(\sum_{j=1}^d \varepsilon_j w_j\right) = \\ &= \sum_{i=1}^d\sum_{j=1}^d (w_i \cdot w_j)\left(\frac{1}{2^d}\sum_{\varepsilon\in\{+1,-1\}^n} \varepsilon_i\varepsilon_j\right) = \sum_{i=1}^d\sum_{j=1}^d (w_i \cdot w_j)\delta_{ij} = \sum_{i=1}^d |w_i|^2 \ge d. \end{aligned}

It follows that there is a ε\varepsilon such that ∣uε∣2≥d|u_\varepsilon|^2 \ge d. For that ε\varepsilon the vector u=uε∣uε∣u = \dfrac{u_\varepsilon}{|u_\varepsilon|} satisfies the conditions.

Transcribed from the official solutions, page 2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?