ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 73812
Темы:    [ Полуинварианты ]
[ Процессы и операции ]
[ Теория алгоритмов (прочее) ]
[ Графы (прочее) ]
Сложность: 4+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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

Решение

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

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1974
выпуск
Номер 8
Задача
Номер М277

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .