Kvant Math Problem 576

Represent each chosen vector by an oriented edge of a directed graph whose vertices are the given points.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 10m41s
Source on kvant.digital

Problem

Several points are given in the plane. For some pairs $(A;B)$ of these points, the vectors $\overrightarrow{AB}$ are taken, in such a way that at each point the number of vectors beginning there is equal to the number of vectors ending there. Prove that the sum of all the chosen vectors is equal to $\overrightarrow{0}$.

V. V. Proizvolov

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

Exploration

Represent each chosen vector by an oriented edge of a directed graph whose vertices are the given points. The condition says that at every vertex, the number of outgoing edges equals the number of incoming edges.

Try a small example. If the chosen vectors are $\overrightarrow{AB},\overrightarrow{BC},\overrightarrow{CA}$, then

$$\overrightarrow{AB}+\overrightarrow{BC}+\overrightarrow{CA} =(\mathbf b-\mathbf a)+(\mathbf c-\mathbf b)+(\mathbf a-\mathbf c) =\mathbf0.$$

The cancellation comes from each point appearing once as an initial point and once as a terminal point.

Consider a more complicated configuration. Suppose two vectors start at $A$ and end at $B$ and $C$, while one vector ends at $A$ from $D$ and another from $E$. Then the contribution of $A$ to the total sum is

$$-2\mathbf a+2\mathbf a=0.$$

Again the cancellation uses only the equality between the numbers of outgoing and incoming vectors.

This suggests assigning to each point $P$ its position vector $\mathbf p$. Every chosen vector $\overrightarrow{AB}$ equals $\mathbf b-\mathbf a$. Summing all chosen vectors gives a sum of position vectors of terminal points minus a sum of position vectors of initial points. Since each point occurs equally many times in both roles, the coefficients cancel.

The only step that could conceal an error is the passage from the geometric vectors to the algebraic expression with position vectors. Once that is written correctly, the coefficient count is straightforward.

Problem Understanding

Several points are fixed in the plane. Some ordered pairs $(A,B)$ are selected, producing vectors $\overrightarrow{AB}$. For every point, the number of selected vectors that begin there equals the number of selected vectors that end there. One must prove that the vector sum of all selected vectors is the zero vector.

This is a Type B problem, a pure proof.

The core difficulty is to convert the local balance condition at each point into a global statement about the sum of all vectors.

Proof Architecture

Let $\mathbf p$ denote the position vector of a point $P$ with respect to an arbitrary origin; then every chosen vector $\overrightarrow{AB}$ equals $\mathbf b-\mathbf a$. The reason is the definition of a vector between two points.

The sum of all chosen vectors can be written as the sum of the position vectors of all terminal points minus the sum of the position vectors of all initial points. This follows by expanding each term $\mathbf b-\mathbf a$.

For every point $P$, the coefficient of $\mathbf p$ in that expanded sum is equal to the number of vectors ending at $P$ minus the number of vectors beginning at $P$. This is obtained by collecting like terms.

The balance condition implies that every such coefficient is zero. Hence the whole sum is the zero vector.

The most delicate point is the coefficient count after expansion.

Solution

Choose an arbitrary origin $O$ in the plane. For each given point $P$, let $\mathbf p=\overrightarrow{OP}$ be its position vector.

For every selected pair $(A,B)$,

$$\overrightarrow{AB} =\overrightarrow{OB}-\overrightarrow{OA} =\mathbf b-\mathbf a.$$

Let $S$ be the sum of all selected vectors. Then

$$S=\sum (\mathbf b-\mathbf a),$$

where the summation extends over all selected pairs $(A,B)$.

Expanding this sum gives

$$S=\sum \mathbf b-\sum \mathbf a.$$

Now collect the coefficients of the position vector of each point. Fix one of the given points $P$. Every selected vector ending at $P$ contributes $+\mathbf p$ to the first sum, and every selected vector beginning at $P$ contributes $-\mathbf p$ to the second sum. Hence the coefficient of $\mathbf p$ in $S$ is

$$(\text{number of vectors ending at }P) - (\text{number of vectors beginning at }P).$$

By the hypothesis of the problem, these two numbers are equal for every point $P$. Therefore the coefficient of $\mathbf p$ is $0$ for every point.

All coefficients in the expansion of $S$ are zero, so

$$S=\mathbf0.$$

Thus the sum of all the chosen vectors is equal to $\overrightarrow{0}$.

This completes the proof.

∎

Verification of Key Steps

The identity

$$\overrightarrow{AB}=\mathbf b-\mathbf a$$

follows directly from

$$\overrightarrow{OA}+\overrightarrow{AB}=\overrightarrow{OB}.$$

Rearranging yields the required formula. No geometric assumption beyond the definition of position vectors is used.

For the coefficient count, suppose a point $P$ is the endpoint of $m$ selected vectors and the initial point of $n$ selected vectors. In the expanded expression

$$\sum \mathbf b-\sum \mathbf a,$$

the vector $\mathbf p$ appears exactly $m$ times with sign $+$ and exactly $n$ times with sign $-$. Hence its coefficient is $m-n$. A careless argument could overlook multiple occurrences of the same point; counting occurrences rather than distinct points avoids that error.

The hypothesis gives $m=n$ for every point. Substituting into $m-n$ yields $0$ point by point. Since every coefficient vanishes individually, no further cancellation between different position vectors is needed.

Alternative Approaches

Interpret the selected vectors as directed edges of a finite directed graph whose vertices are the given points. The condition states that each vertex has equal indegree and outdegree. Such a graph is a union of directed cycles. The vector sum along any directed cycle is zero, because for a cycle

$$A_1A_2,\ A_2A_3,\ \ldots,\ A_kA_1,$$

one has

$$\overrightarrow{A_1A_2} +\overrightarrow{A_2A_3} +\cdots+ \overrightarrow{A_kA_1} =\mathbf0.$$

Summing over all cycles gives the result.

This approach is elegant, but it requires the additional fact that every finite directed graph with equal indegree and outdegree at each vertex decomposes into directed cycles. The position-vector argument proves the statement directly and with less machinery.