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