Олимпиадная задача о перекрёстках и цветах улиц Дужинска: теория графов для 9–11 классов

Решение 1:   Заменим каждую белую улицу города на две – синюю и красную, соединив синим цветом концы синих улиц, соседних с белой, а красным цветом – концы соседних с ней красных улиц (см. рис.). В соответствии с этими рисунками будем называть белые улицы улицами типов а, б, в и г, а их количества обозначим соответственно n_а, n_б, n_в и n_г. В случаях, изображённых на центральных рисунках, будем считать, что красная и синяя улицы, которыми мы заменили белую, пересекаются в точке, отличной от вершин ломаных, которыми являются эти улицы.

  Теперь все синие улицы образуют несколько многоугольников. Назовём ихсиними. Аналогично красные улицы образуют несколькокрасныхмногоугольников. Ясно, что границы двух многоугольников разного цвета либо не пересекаются, либо пересекаются в чётном числе точек (если границы пересекаются, то граница одного из многоугольников входит внутрь второго столько же раз, сколько и выходит из него). Но число точек пересечения границ многоугольников разного цвета равно  n_б+n_в.  Значит, число  n_б+n_в– чётное. Осталось заметить, что разность между числом положительных и числом отрицательных перекрёстков равна  2(n_б–n_в) = 2(n_б+n_в) – 4n_в  и, следовательно, кратна 4.

Решение 2:   Рассмотрим произвольную (например, белую) улицу, соединяющую положительный и отрицательный перекрёстки A и B, если такая улица в городе есть. Удалим эти перекрёстки и все улицы, ведущие из A в B. Оставшиеся улицы одного цвета соединим между собой тем же цветом (см. рисунки; ∅ – обозначение пустого множества).

  При этом справедливость условий задачи не нарушается, а разность между числом положительных и числом отрицательных перекрёстков сохраняется. Будем продолжать эту процедуру до тех пор, пока это возможно. Без ограничения общности можно считать, что в городе остались только положительные перекрёстки. (Вообще говоря, город теперь состоит из нескольких не связанных между собой частей, в каждой из которых все перекрёстки либо положительные, либо отрицательные. Отрицательные перекрёстки, если они есть, мы будем выбрасывать по той же самой схеме, которая описана ниже для положительных перекрёстков.)   Рассмотрим произвольный такой перекрёсток и три перекрёстка, соединённые с ним (очевидно, что в любом удовлетворяющем условию задачи городе, в котором все перекрестки положительны, можно найти такие четыре перекрёстка; эти перекрёстки не обязательно должны быть различными). Удалим эти четыре перекрёстка и все соединяющие их улицы. Оставшиеся улицы одного цвета соединим между собой тем же цветом (см. рис.).  При этом снова не нарушается справедливость условий задачи, а число положительных перекрёстков уменьшается на 4. Эту операцию можно продолжать до тех пор, пока улиц в городе не останется вовсе. Но тогда разность между числом положительных и отрицательных перекрёстков станет равна нулю. Следовательно, первоначально (для исходного города) эта разность была кратна 4.

Ответ задачи отсутствует