Kvant Math Problem 277

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

Problem

Several red points and several blue points are given. Some pairs of points are connected by line segments. Call a point special if more than half of the points connected to it have a color different from its own. If there is at least one special point, then an arbitrary special point is chosen and recolored to the other color. Prove that after a finite number of steps there will be no special points left.

A. M. Steinberg

All-Union Mathematical Olympiad for School Students (1974, Grade 10)

Exploration

Let $E$ be the number of segments whose endpoints have different colors. The process changes the color of one special vertex. A natural conjecture is that $E$ decreases every time.

Take a special vertex $v$. Let $a$ be the number of neighbors of the same color as $v$, and let $b$ be the number of neighbors of the opposite color. Since $v$ is special, $b>a$.

Before recoloring $v$, exactly the $b$ edges from $v$ to opposite-colored neighbors contribute to $E$. After recoloring, those $b$ edges become monochromatic, while the $a$ edges to formerly same-colored neighbors become bichromatic. Thus the contribution of edges incident with $v$ to $E$ changes from $b$ to $a$.

The net change is

$$E_{\text{new}}-E_{\text{old}}=a-b<0.$$

Since only edges incident with $v$ can change their status, $E$ strictly decreases.

This looks promising because $E$ is a nonnegative integer. If it strictly decreases at every step, the process cannot continue forever.

To test the idea, consider a path of two vertices of different colors. Both vertices are special. Recoloring either vertex changes $E$ from $1$ to $0$, and the process stops. For a triangle with two red vertices and one blue vertex, the blue vertex is special; recoloring it makes all vertices red and changes $E$ from $2$ to $0$. Again $E$ decreases.

The only potentially dangerous point is verifying that no edges other than those incident with the recolored vertex affect $E$. Since colors of all other vertices remain unchanged, every other edge keeps the same pair of endpoint colors, so its contribution indeed remains unchanged.

The core insight is that the number of bichromatic edges is a strictly decreasing integer-valued potential function.

Problem Understanding

We have a graph whose vertices are colored red or blue. A vertex is called special when a strict majority of its neighbors have the opposite color. At each step, if at least one special vertex exists, one such vertex is chosen arbitrarily and its color is switched.

We must prove that regardless of the choices made, the procedure cannot continue indefinitely. After finitely many recolorings, a configuration with no special vertices must be reached.

This is a Type B problem. The main difficulty is finding a quantity that changes monotonically under every allowed recoloring, independently of which special vertex is chosen.

Proof Architecture

Define $E$ as the number of edges whose endpoints have different colors; prove that $E$ is a nonnegative integer.

Show that recoloring a vertex affects only the edges incident with that vertex, because all other endpoint colors remain unchanged.

For a special vertex $v$, let $a$ be the number of neighbors of the same color and $b$ the number of neighbors of the opposite color; prove that $b>a$.

Compute the change in $E$ under recoloring $v$ and show that

$$E_{\text{new}}=E_{\text{old}}-(b-a),$$

hence $E_{\text{new}}<E_{\text{old}}$.

Conclude that $E$ decreases by at least $1$ at every step and cannot decrease infinitely often because $E\ge0$.

Deduce that only finitely many recolorings are possible; when the process stops, no special vertex exists.

The most delicate point is the computation of the change in $E$, because it must account for all affected edges and no others.

Solution

Let $E$ denote the number of segments whose endpoints have different colors. Since the number of segments is finite, $E$ is a finite nonnegative integer.

Suppose a step of the procedure is performed. Let $v$ be the chosen special point. Denote by $a$ the number of points connected to $v$ that have the same color as $v$, and by $b$ the number of points connected to $v$ that have the opposite color.

Because $v$ is special, more than half of its neighbors have the opposite color. Hence

$$b>a.$$

We compare the value of $E$ before and after recoloring $v$.

Only segments incident with $v$ can change their contribution to $E$, because the colors of all other vertices remain unchanged. Every segment not incident with $v$ has the same pair of endpoint colors before and after the recoloring.

Before recoloring, each of the $b$ segments joining $v$ to an opposite-colored neighbor contributes $1$ to $E$, while each of the $a$ segments joining $v$ to a same-colored neighbor contributes $0$.

After recoloring, the situation is reversed. The $b$ former bichromatic segments become monochromatic and contribute $0$, while the $a$ former monochromatic segments become bichromatic and contribute $1$.

Therefore the total contribution of segments incident with $v$ changes from $b$ to $a$. Consequently,

$$E_{\text{new}}=E_{\text{old}}-b+a =E_{\text{old}}-(b-a).$$

Since $b>a$,

$$b-a\ge1,$$

and thus

$$E_{\text{new}}<E_{\text{old}}.$$

Hence every recoloring step strictly decreases the nonnegative integer $E$.

A strictly decreasing sequence of nonnegative integers is finite. Therefore only finitely many recolorings can occur.

The procedure stops exactly when there is no special point, because a recoloring is performed whenever at least one special point exists. Since infinitely many recolorings are impossible, after a finite number of steps a configuration with no special points is reached.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is showing that only edges incident with the recolored vertex matter. Consider any edge not incident with $v$. Neither endpoint changes color during the step. Hence the two endpoint colors are identical before and after the recoloring, so the edge either contributes to $E$ both times or contributes neither time. Any argument that counts changes on nonincident edges would be introducing effects that do not exist.

The second delicate step is the calculation of the change in $E$. Let $a=2$ and $b=5$ as a concrete example. Before recoloring, the incident contribution is $5$. After recoloring, it is $2$. The decrease is $3=b-a$. The general formula is exactly the same count. Forgetting that the $a$ edges become bichromatic after recoloring would incorrectly predict a decrease of $b$ instead of $b-a$.

The third delicate step is converting “more than half of the neighbors have opposite color” into a strict decrease. The condition means $b>a$, not merely $b\ge a$. If equality were allowed, $E$ could remain unchanged. The strict majority condition guarantees $b-a\ge1$, which yields a strictly decreasing integer potential.

Alternative Approaches

One may define a potential function

$$\Phi=\sum_{uv} \chi(u,v),$$

where the sum runs over all edges and $\chi(u,v)=1$ if the endpoints have different colors and $\chi(u,v)=0$ otherwise. This is exactly the quantity $E$ used above, written as a sum of local contributions. Recoloring a special vertex changes the contribution of each incident edge, and the total change equals $a-b<0$.

Another viewpoint is to count, for every vertex, the number of neighbors of the opposite color and sum these numbers over all vertices. This quantity equals $2E$. Recoloring a special vertex decreases this sum by $2(b-a)>0$. Since the sum is a nonnegative integer, termination follows exactly as before. The proof using $E$ is preferable because it works directly with the graph's bichromatic edges and requires the least computation.