Problem

Source: 1998 Estonia National Olympiad Final Round grade 10 p5

Tags: combinatorics, Coloring



The paper is marked with the finite number of blue and red dots and some these points are connected by lines. Let's name a point $P$ special if more than half of the points connected with $P$ has a color other than point $P$. Juku selects one special point and reverses its color. Then Juku selects a new special point and changes its color, etc. Prove that by a finite number of integers Juku ends up in a situation where the paper has not made a special point.