Условие
Улицы города Дужинска – простые ломаные, не пересекающиеся между собой во внутренних точках. Каждая улица соединяет два перекрёстка и покрашена в один из трёх цветов: белый, красный или синий. На каждом перекрёстке сходятся ровно три улицы, по одной каждого цвета. Перекрёсток называется положительным, если при его обходе против часовой стрелки цвета улиц идут в следующем порядке: белый, синий, красный, и отрицательным в противном случае. Докажите, что разность между числом положительных и числом отрицательных перекрёстков кратна 4.
Решение 1
Заменим каждую белую улицу города на две – синюю и красную, соединив синим цветом концы синих улиц, соседних с белой, а красным цветом – концы соседних с ней красных улиц (см. рис.). В соответствии с этими рисунками будем называть белые улицы улицами типов а, б, в и г, а их
количества обозначим соответственно nа, nб, nв и nг. В случаях, изображённых на
центральных рисунках, будем считать, что красная и синяя улицы, которыми мы заменили белую, пересекаются в точке, отличной от вершин ломаных, которыми являются эти улицы.
Теперь все синие улицы образуют несколько многоугольников. Назовём их
синими. Аналогично красные улицы образуют несколько
красных многоугольников. Ясно, что границы двух многоугольников разного цвета либо не пересекаются, либо пересекаются в чётном числе точек (если границы пересекаются,
то граница одного из многоугольников входит внутрь второго столько же раз, сколько и выходит из него). Но число точек пересечения границ многоугольников разного цвета равно
nб +
nв. Значит, число
nб +
nв – чётное.
Осталось заметить, что разность между числом положительных и числом отрицательных перекрёстков равна 2(
nб –
nв) = 2(
nб +
nв) – 4
nв и, следовательно, кратна 4.
Решение 2
Рассмотрим произвольную (например, белую) улицу, соединяющую положительный и отрицательный перекрёстки A и B, если такая улица в городе есть. Удалим эти перекрёстки и все улицы, ведущие из A в B. Оставшиеся улицы одного цвета соединим между собой тем же цветом
(см. рисунки; ∅ – обозначение пустого множества).
При этом справедливость условий задачи не нарушается, а разность между числом положительных и числом отрицательных перекрёстков сохраняется. Будем продолжать эту процедуру до тех пор, пока это возможно. Без ограничения общности можно считать, что в городе остались только положительные перекрёстки.
(Вообще говоря, город теперь состоит из нескольких не связанных между собой частей, в каждой из которых все перекрёстки либо положительные, либо отрицательные. Отрицательные перекрёстки, если они есть, мы будем выбрасывать по той же самой схеме, которая описана ниже для положительных перекрёстков.)
Рассмотрим произвольный такой перекрёсток и три перекрёстка, соединённые с ним (очевидно, что в любом удовлетворяющем условию задачи городе, в котором все перекрестки положительны, можно найти такие четыре перекрёстка; эти перекрёстки не обязательно должны быть различными). Удалим эти четыре перекрёстка и все соединяющие их улицы. Оставшиеся улицы одного
цвета соединим между собой тем же цветом (см. рис.).
При этом снова не нарушается справедливость условий задачи, а число положительных перекрёстков уменьшается на 4. Эту операцию можно продолжать до тех пор, пока улиц в городе не останется вовсе. Но тогда разность между числом положительных и отрицательных перекрёстков станет равна нулю. Следовательно, первоначально (для исходного города) эта разность была кратна 4.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
1995 |
|
Этап |
|
Вариант |
4 |
|
Класс |
|
Класс |
10 |
|
задача |
|
Номер |
95.4.10.8 |
|
|
|
|
олимпиада |
|
Название |
Всероссийская олимпиада по математике |
|
год |
|
Год |
1995 |
|
Этап |
|
Вариант |
4 |
|
Класс |
|
Класс |
11 |
|
задача |
|
Номер |
95.4.11.8 |
