Особые точки и перекрашивание — олимпиадная задача по комбинаторной ге
Задача
На плоскости даны 10 точек: несколько из них – белые, а остальные – чёрные. Некоторые точки соединены отрезками. Назовём точку особой, если более половины соединенных с ней точек имеют цвет, отличный от её цвета. Каждым ходом выбирается одна из особых точек (если такие есть) и перекрашивается в противоположный цвет. Докажите, что через несколько ходов не останется ни одной особой точки.
Решение
Допустим, что в какой-то момент мы перекрашиваем особую точку A (для определенности, пусть эта особая точка до перекрашивания была белой). Пусть точка A соединена с m белыми и n черными точками; m < n согласно определению особой точки. Поэтому после перекрашивания особой точки количество отрезков, имеющих один белый и один чёрный конец, уменьшается (до перекрашивания из точки A выходило n таких отрезков, а после – только m). Поскольку число отрезков конечно, через несколько перекрашиваний мы не сможем сделать больше ни одного, то есть особых точек не останется.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь