Условие
Задано несколько красных и несколько синих точек. Некоторые из них соединены отрезками. Назовём точку «особой», если более половины из соединённых с ней точек имеют цвет, отличный от её цвета. Если есть хотя бы одна особая точка, то выбираем любую особую точку и перекрашиваем в другой цвет. Докажите, что через конечное число шагов не останется ни одной особой точки.
Решение
Назовем отрезок "любым", если его концы имеют разный цвет. Заметим, что точка
является "особой", если более половины выходящих из нее отрезков– "особые".
Поэтому при перекрашивании любой "особой" точки общее число "особых"
отрезков уменьшается. Поскольку всего "особых" отрезков не меньше нуля,
а при каждом шаге их число уменьшается по крайней мере на единицу, мы через
конечное число шагов получим систему, в которой ни одну из точек перекрасить
нельзя и, следовательно, нет особых точек.
Источники и прецеденты использования
