Условие задачи (1974, № 8) Задача М277 // Квант. — 1974. — № 8. — Стр. 44; 1975. — № 3. — Стр. 51.
Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Назовём точку «особой», если более половины из соединённых с ней точек имеют цвет, отличный от её цвета. Если есть хотя бы одна особая точка, то выбирается любая особая точка и перекрашивается в другой цвет. Докажите, что через конечное число шагов не останется ни одной особой точки.
Изображения страниц
Решение задачи (1975, № 3) Задача М277 // Квант. — 1974. — № 8. — Стр. 44; 1975. — № 3. — Стр. 51.
Назовём отрезок «особым», если его концы имеют разный цвет. Заметим, что точка является «особой», если более половины выходящих из неё отрезков — «особые». Поэтому при перекрашивании любой «особой» точки общее число «особых» отрезков уменьшается. Поскольку всего «особых» отрезков не меньше нуля, а при каждом шаге их число уменьшается по крайней мере на единицу, мы через конечное число шагов получим систему, в которой ни одну из точек перекрасить нельзя и, следовательно, нет особых точек.