Kvant Math Problem 573

Let the lines through $O$ be $l_1,\dots,l_{1979}$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m24s
Source on kvant.digital

Problem

Through the point $O$, 1979 lines are drawn

  1. in the plane,
  2. in space,

with no two of them perpendicular to each other. On the line $l_1$, choose an arbitrary point $A_1$ distinct from $O$. Prove that it is possible to choose on each of the remaining lines a point $A_i \in l_i$ ($i=2$, 3, $\ldots$, 1979) so that the following 1979 pairs of lines are mutually perpendicular: $$\begin{gathered} (A_1A_3)\perp l_2,\quad (A_2A_4)\perp l_3,\quad\ldots,\quad (A_{i-1}A_{i+1}) \perp l_i,\quad\ldots\\ldots,\quad (A_{1977}A_{1979})\perp l_{1978},\quad (A_{1978}A_1)\perp l_{1979},\quad (A_{1979}A_2)\perp l_1. \end{gathered}$$

B. Agafonov

All-Union Mathematical Olympiad for School Students (1979, Grade 9)

Exploration

Let the lines through $O$ be $l_1,\dots,l_{1979}$. Write each point in the form

$$A_i=x_iu_i,$$

where $u_i$ is a fixed nonzero direction vector of $l_i$ and $x_i$ is a scalar.

The condition

$$(A_{i-1}A_{i+1})\perp l_i$$

means that the vector

$$A_{i+1}-A_{i-1}$$

is orthogonal to $u_i$. Hence

$$u_i\cdot(A_{i+1}-A_{i-1})=0.$$

Substituting $A_j=x_ju_j$ gives

$$(u_i\cdot u_{i+1})x_{i+1}-(u_i\cdot u_{i-1})x_{i-1}=0.$$

Because no two lines are perpendicular, every scalar product

$u_i\cdot u_j$ is nonzero.

Thus we obtain a homogeneous linear system involving only variables of the same parity. Since $1979$ is odd, repeated use of the relations should propagate all variables from $x_1$.

Try a smaller case, $n=5$:

$$c_1x_2=d_1x_5,\qquad c_2x_3=d_2x_1,\qquad c_3x_4=d_3x_2,$$

$$c_4x_5=d_4x_3,\qquad c_5x_1=d_5x_4,$$

where $c_i=u_i\cdot u_{i+1}$ and $d_i=u_i\cdot u_{i-1}$.

Starting from $x_1$, all other variables are determined uniquely:

$$x_3=\frac{d_2}{c_2}x_1,\quad x_5=\frac{d_4}{c_4}x_3,\quad x_2=\frac{d_1}{c_1}x_5,\quad x_4=\frac{d_3}{c_3}x_2.$$

The last equation becomes

$$c_5x_1=d_5x_4.$$

After substitution, the coefficient multiplying $x_1$ is

$$\frac{d_1d_2d_3d_4d_5}{c_1c_2c_3c_4c_5}.$$

But

$$d_i=u_i\cdot u_{i-1}=u_{i-1}\cdot u_i=c_{i-1},$$

so the numerator and denominator are the same cyclic product. Hence the final equation is automatically satisfied.

This suggests the general mechanism. The crucial point is proving that the consistency condition obtained after one full cycle reduces to an identity because

$$d_i=c_{i-1}.$$

The same algebra works in the plane and in space, since only scalar products are used.

Problem Understanding

We are given $1979$ distinct lines through a common point $O$, either in a plane or in three-dimensional space. No two lines are perpendicular.

A point $A_1\neq O$ is fixed on $l_1$. We must choose points $A_i\in l_i$ for $i\ge2$ so that for every index $i$ taken cyclically modulo $1979$,

$$(A_{i-1}A_{i+1})\perp l_i.$$

This is a Type D problem. We must show that such a choice exists.

The core difficulty is that the perpendicularity conditions form a cyclic system. After expressing the unknown points by coordinates on their lines, one obtains a homogeneous linear recurrence. The main issue is proving that the cyclic closure condition is automatically satisfied.

Proof Architecture

Choose a nonzero direction vector $u_i$ on each line $l_i$ and write $A_i=x_i u_i$.

The condition $(A_{i-1}A_{i+1})\perp l_i$ is equivalent to

$$(u_i\cdot u_{i+1})x_{i+1}=(u_i\cdot u_{i-1})x_{i-1}.$$

Since no two lines are perpendicular, every coefficient $u_i\cdot u_j$ occurring in these equations is nonzero.

Define

$$c_i=u_i\cdot u_{i+1}.$$

Then the relations become

$$c_i x_{i+1}=c_{i-1}x_{i-1}.$$

Because $1979$ is odd, repeated application of these relations determines all variables uniquely from $x_1$.

The final cyclic equation is automatically satisfied because the product of all factors accumulated during the propagation equals

$$\frac{c_1c_2\cdots c_{1979}}{c_1c_2\cdots c_{1979}}=1.$$

The most delicate step is verifying this cyclic consistency identity.

Solution

Choose on each line $l_i$ a nonzero direction vector $u_i$. Since $A_1\neq O$ is already fixed, there exists a nonzero scalar $x_1$ such that

$$A_1=x_1u_1.$$

For $i\ge2$ we shall seek points in the form

$$A_i=x_i u_i,$$

where the scalars $x_i$ are unknown.

The condition

$$(A_{i-1}A_{i+1})\perp l_i$$

means that the vector

$$A_{i+1}-A_{i-1}$$

is orthogonal to the direction vector $u_i$. Hence

$$u_i\cdot(A_{i+1}-A_{i-1})=0.$$

Substituting $A_j=x_j u_j$, we obtain

$$(u_i\cdot u_{i+1})x_{i+1} = (u_i\cdot u_{i-1})x_{i-1}.$$

Set

$$c_i=u_i\cdot u_{i+1},$$

where the indices are taken cyclically modulo $1979$. Since no two lines are perpendicular, every $c_i$ is nonzero. Also,

$$u_i\cdot u_{i-1} = u_{i-1}\cdot u_i = c_{i-1}.$$

Therefore the perpendicularity conditions are equivalent to

$$c_i x_{i+1}=c_{i-1}x_{i-1}, \qquad i=1,\dots,1979.$$

From these equations,

$$x_{i+1}=\frac{c_{i-1}}{c_i}x_{i-1}.$$

Because $1979$ is odd, the step $i\mapsto i+2$ generates all residue classes modulo $1979$. Starting from the prescribed value $x_1$, the above relations determine successively

$$x_3,\ x_5,\ \dots,\ x_{1979},\ x_2,\ x_4,\ \dots,\ x_{1978}.$$

Thus all $x_i$ are defined.

It remains to verify that the last equation of the cyclic system is satisfied automatically. Following one complete cycle, we obtain

$$x_1 = \frac{c_{1979}}{c_1} \frac{c_1}{c_2} \frac{c_2}{c_3} \cdots \frac{c_{1978}}{c_{1979}} x_1.$$

The product on the right telescopes:

$$\frac{c_{1979}c_1c_2\cdots c_{1978}} {c_1c_2\cdots c_{1978}c_{1979}} =1.$$

Hence the resulting identity is

$$x_1=x_1.$$

Therefore the final cyclic equation imposes no additional restriction, and all equations

$$c_i x_{i+1}=c_{i-1}x_{i-1}$$

hold simultaneously.

Define

$$A_i=x_i u_i \qquad (i=2,\dots,1979).$$

For every $i$,

$$c_i x_{i+1}=c_{i-1}x_{i-1}$$

is equivalent to

$$u_i\cdot(A_{i+1}-A_{i-1})=0,$$

which is equivalent to

$$(A_{i-1}A_{i+1})\perp l_i.$$

Thus all required perpendicularities are satisfied.

The argument uses only scalar products and the fact that none of them is zero, so it is valid both in the plane and in space.

The required points therefore exist. $\boxed{A_1,A_2,\dots,A_{1979}}$

Verification of Key Steps

The first delicate point is the translation of the geometric condition into algebra. The line through $A_{i-1}$ and $A_{i+1}$ has direction vector

$$A_{i+1}-A_{i-1}.$$

A line is perpendicular to $l_i$ precisely when its direction vector is orthogonal to a direction vector of $l_i$. Hence

$$(A_{i-1}A_{i+1})\perp l_i \iff u_i\cdot(A_{i+1}-A_{i-1})=0.$$

No geometric assumption beyond the definition of perpendicularity is used.

The second delicate point is the propagation of the variables. Since $1979$ is odd,

$$\gcd(2,1979)=1.$$

Consequently the sequence

$$1,3,5,\dots$$

taken modulo $1979$ visits every index exactly once. Starting from $x_1$, the recurrence

$$x_{i+1}=\frac{c_{i-1}}{c_i}x_{i-1}$$

indeed determines every variable.

The third delicate point is the consistency check. After traversing all $1979$ indices, the accumulated multiplier is

$$\prod_{i=1}^{1979}\frac{c_{i-1}}{c_i}.$$

The numerator and denominator contain exactly the same factors, merely in a cyclic order. Their ratio equals $1$, so the cycle closes without contradiction.

Alternative Approaches

The system may be viewed as a homogeneous linear system in the variables $x_i$. Since all coefficients are nonzero, each equation expresses one variable through another two steps away. Because the number of indices is odd, the associated graph is a single cycle. Computing the determinant condition for consistency yields exactly the cyclic product identity

$$\prod_{i=1}^{1979} c_{i-1} = \prod_{i=1}^{1979} c_i,$$

which holds trivially. Hence the solution space is one-dimensional, and prescribing $A_1$ selects a unique solution.

The recurrence approach is preferable because it avoids determinant calculations and exhibits directly how the points are constructed from the given point $A_1$. This provides existence and construction simultaneously.