Track / Stage 6 / 35 of 400 #1035 of 1964

Problem 1035

National olympiad, first round

Combinatorics Difficulty 6.0 Prove it

On the plane, there are 10 points: some of them are white, and the others are black. Some points are connected by segments. We will call a point special if more than half of the points connected to it have a color different from its own color. Each move involves selecting one of the special points (if any exist) and recoloring it to the opposite color. Prove that after several moves, there will be no special points left.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

At the moment of recoloring a special point, the number of segments with ends of different colors decreases.

## Solution

Suppose that at some point we recolor a special point $A$ (for definiteness, let this special point be white before recoloring). Let point $A$ be connected to $m$ white and $n$ black points; $m < n$ according to the definition of a special point. Therefore, after recoloring the special point, the number of segments with one white and one black end decreases (before recoloring, $n$ such segments were coming out of point $A$ , and after - only $m$ ). Since the number of segments is finite, after several recolorings we will not be able to perform any more, that is, there will be no special points left.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.