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

   Решение

Тема:    [ Соображения непрерывности ]

Сложность: 3 Классы: 7,8

Прислать комментарий

Условие

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

Подсказка

Двигайте сержанта вдоль строя. Число стоящих лицом к сержанту при этом меняется не более чем на 1.

Решение

  Для каждого положения сержанта в строю вычислим разность d между количеством человек, стоящих слева от сержанта к нему лицом, и количеством человек, стоящих справа от сержанта к нему лицом. Посмотрим, как это число меняется при сдвиге сержанта на одно место вправо. Если он "проходит" новобранца, стоявшего к нему спиной, то d увеличивается на 1. Если сержант "проходит" новобранца, стоявшего к нему лицом, то d уменьшается на 1. Иначе d не меняется.
  Ясно также, что, когда сержант стоит крайним слева, d неположительно, а когда он стоит крайним справа, d неотрицательно. Поскольку на каждом шаге d меняется не более чем на 1, где-то "по дороге" оно примет значение 0. В этом положении с обеих сторон от сержанта лицом к нему находится поровну новобранцев.

Ответ

Всегда.

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