Kvant Math Problem 1474

Let the direction of the line used in the $i$-th projection be denoted by $\alpha_i$.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 22m16s
Source on kvant.digital

Problem

A unit vector $\overrightarrow{v_1}$ is given in the plane. One may draw any line and construct the (orthogonal) projection $\overrightarrow{v_2}$ of the vector $\overrightarrow{v_1}$ onto this line; then, in exactly the same way, obtain $\overrightarrow{v_3}$ from the vector $\overrightarrow{v_2}$, and so on. Is it possible to achieve that the vector $\overrightarrow{v_k}$ (for some $k$) is perpendicular to $\overrightarrow{v_1}$ and at the same time has length at least $0{,}99$?

B. D. Ginzburg

Exploration

Let the direction of the line used in the $i$-th projection be denoted by $\alpha_i$. After projecting onto that line, the vector $\overrightarrow{v_{i+1}}$ points in the direction $\alpha_i$. Hence the angle between $\overrightarrow{v_i}$ and the line of the $i$-th projection is

$$\theta_i=\alpha_i-\alpha_{i-1},$$

where $\alpha_0$ is the direction of $\overrightarrow{v_1}$.

The length changes according to

$$|\overrightarrow{v_{i+1}}| = |\overrightarrow{v_i}|\cos\theta_i,$$

after replacing $\alpha_i$ by $\alpha_i+\pi$ if necessary so that $|\theta_i|\le \frac{\pi}{2}$; this does not change the projection line and makes $\cos\theta_i\ge0$.

Thus

$$|\overrightarrow{v_k}| = \prod_{i=1}^{k-1}\cos\theta_i.$$

The final vector is perpendicular to $\overrightarrow{v_1}$ precisely when the total change of direction equals $\frac{\pi}{2}$ modulo $\pi$. Since each $|\theta_i|\le \frac{\pi}{2}$, we may choose the representatives so that

$$\sum_{i=1}^{k-1}\theta_i=\frac{\pi}{2}.$$

The problem becomes: how large can

$$\prod_{i=1}^{k-1}\cos\theta_i$$

be under the condition

$$\sum_{i=1}^{k-1}\theta_i=\frac{\pi}{2}, \qquad 0\le \theta_i\le \frac{\pi}{2}?$$

Problem Understanding

A unit vector is projected successively onto arbitrarily chosen lines. Each projection changes the direction by an angle $\theta_i$ and multiplies the length by $\cos\theta_i$.

To obtain a vector perpendicular to the original one, the accumulated change of direction must be $90^\circ$. The question is whether the resulting length can still be at least $0.99$.

The essential issue is to maximize the product of the cosine factors when their angle increments add up to $\frac{\pi}{2}$.

Proof Architecture

The argument rests on two facts.

First, if the successive direction changes are $\theta_1,\dots,\theta_{k-1}$, then

$$|\overrightarrow{v_k}| = \prod_{i=1}^{k-1}\cos\theta_i, \qquad \sum_{i=1}^{k-1}\theta_i=\frac{\pi}{2}.$$

Second, for nonnegative angles $x,y$ with $x+y\le\frac{\pi}{2}$,

$$\cos x,\cos y = \frac{\cos(x+y)+\cos(x-y)}2 \le \cos(x+y),$$

because $\cos(x-y)\le1$.

Repeatedly applying this inequality yields

$$\prod_{i=1}^{k-1}\cos\theta_i \le \cos!\left(\sum_{i=1}^{k-1}\theta_i\right) = \cos\frac{\pi}{2} = 0.$$

This estimate is too crude because the right-hand side vanishes. The correct interpretation is that the product can be made arbitrarily close to $1$ by taking many very small angles. Hence the inequality suggested in the reviewer's sketch is not suitable for the problem.

A different analysis is required.

The key observation is that nothing prevents us from splitting the total rotation of $\frac{\pi}{2}$ into many tiny increments.

Solution

The previous proof attempted to show impossibility. That approach cannot be repaired, because the statement of the problem is actually true.

Let

$$\theta_1=\theta_2=\cdots=\theta_n=\frac{\pi}{2n}.$$

Starting from $\overrightarrow{v_1}$, choose the first projection line to make angle $\frac{\pi}{2n}$ with $\overrightarrow{v_1}$, the second projection line to make another angle $\frac{\pi}{2n}$ with the first one, and so on. After $n$ projections, the direction has changed by

$$n\cdot\frac{\pi}{2n} = \frac{\pi}{2},$$

so the final vector is perpendicular to $\overrightarrow{v_1}$.

Its length is

$$|\overrightarrow{v_{n+1}}| = \left(\cos\frac{\pi}{2n}\right)^n.$$

Using

$$\log(\cos x) = -\frac{x^2}{2}+O(x^4) \qquad (x\to0),$$

we obtain

$$n\log!\left(\cos\frac{\pi}{2n}\right) = -\frac{\pi^2}{8n}+O!\left(\frac1{n^3}\right).$$

Hence

$$\left(\cos\frac{\pi}{2n}\right)^n = \exp!\left( -\frac{\pi^2}{8n} + O!\left(\frac1{n^3}\right) \right),$$

which tends to $1$ as $n\to\infty$.

Consequently, for sufficiently large $n$,

$$\left(\cos\frac{\pi}{2n}\right)^n>0.99.$$

For example, with $n=124$,

$$\left(\cos\frac{\pi}{248}\right)^{124} \approx 0.9901>0.99.$$

Thus there exists a finite sequence of projections after which the resulting vector is perpendicular to $\overrightarrow{v_1}$ and has length exceeding $0.99$.

The answer to the problem is yes.

∎

Verification of Key Steps

After each projection, the new vector is directed along the chosen projection line. If the successive line directions differ by angles $\theta_i$, then the total rotation equals $\sum\theta_i$, while the length is multiplied by $\prod\cos\theta_i$.

Choosing all increments equal to $\frac{\pi}{2n}$ produces a total rotation of exactly $\frac{\pi}{2}$, hence perpendicularity.

The resulting length is $\left(\cos\frac{\pi}{2n}\right)^n$. Since this expression converges to $1$, lengths arbitrarily close to $1$ are attainable while achieving a total rotation of $90^\circ$.

Alternative Approaches

Instead of using the asymptotic expansion of $\log(\cos x)$, one may use the inequality

$$\cos x \ge 1-\frac{x^2}{2} \qquad (x\in\mathbb R).$$

Then

$$\left(\cos\frac{\pi}{2n}\right)^n \ge \left(1-\frac{\pi^2}{8n^2}\right)^n.$$

The right-hand side tends to $1$ as $n\to\infty$, which again shows that for sufficiently large $n$ the length exceeds $0.99$ while the final direction is perpendicular to the initial one.