ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 109870
УсловиеУлицы города Дужинска – простые ломаные, не пересекающиеся между собой во внутренних точках. Каждая улица соединяет два перекрёстка и покрашена в один из трёх цветов: белый, красный или синий. На каждом перекрёстке сходятся ровно три улицы, по одной каждого цвета. Перекрёсток называется положительным, если при его обходе против часовой стрелки цвета улиц идут в следующем порядке: белый, синий, красный, и отрицательным в противном случае. Докажите, что разность между числом положительных и числом отрицательных перекрёстков кратна 4. Решение 1Заменим каждую белую улицу города на две – синюю и красную, соединив синим цветом концы синих улиц, соседних с белой, а красным цветом – концы соседних с ней красных улиц (см. рис.). В соответствии с этими рисунками будем называть белые улицы улицами типов а, б, в и г, а их количества обозначим соответственно nа, nб, nв и nг. В случаях, изображённых на центральных рисунках, будем считать, что красная и синяя улицы, которыми мы заменили белую, пересекаются в точке, отличной от вершин ломаных, которыми являются эти улицы. Решение 2Рассмотрим произвольную (например, белую) улицу, соединяющую положительный и отрицательный перекрёстки A и B, если такая улица в городе есть. Удалим эти перекрёстки и все улицы, ведущие из A в B. Оставшиеся улицы одного цвета соединим между собой тем же цветом (см. рисунки; ∅ – обозначение пустого множества). Рассмотрим произвольный такой перекрёсток и три перекрёстка, соединённые с ним (очевидно, что в любом удовлетворяющем условию задачи городе, в котором все перекрестки положительны, можно найти такие четыре перекрёстка; эти перекрёстки не обязательно должны быть различными). Удалим эти четыре перекрёстка и все соединяющие их улицы. Оставшиеся улицы одного цвета соединим между собой тем же цветом (см. рис.). Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |