The streets of the city of Duzhinsk are simple polygonal lines not intersecting each other in internal points. Each street connects two crossings and is colored in one of three colors: white, red, or blue. At each crossing exactly three streets meet, one of each color. A crossing is called positive if the streets meeting at it are white, blue and red in counterclockwise direction, and negative otherwise. Prove that the difference between the numbers of positive and negative crossings is a multiple of 4.
Problem
Source: Russia 1995
Tags: combinatorics unsolved, combinatorics
18.10.2008 20:34
(WLOG) Ignore all of the blue streets. Then the white and red streets form a series of alternating edge-colored polygons, as each intersection must have one white and one red street and the streets cannot cross. Also, the polygons are non-intersecting, and they each have an even number of edges. Consider all polygons $ P$ which are not enclosed by any polygons, and going clockwise around the vertices, alternately label them $ A$ and $ B$, such that (wlog) each $ A$ is between a white and red street in that order. Repeat this step on any polygons enclosed by the above polygons, except reverse the $ A$s and $ B$s such that each $ A$ is now between a red and white street in that order, and so forth continue labeling all of the vertices, alternating the order with each 'level'. It is easy to see now that if 2 $ A$s or 2 $ B$s are connected by a blue street, then they have the same sign (consider if the blue path is within a polygon, between two polygons, or between a polygon and the polygon enclosing it), and if an $ A$ and $ B$ are connected they have opposite signs. We ignore the case with opposite signs because they do not change the difference. There are the same number of $ A$s and $ B$s, and after removing the pairs of points with opposite signs, there still are the same number of $ A$s and $ B$s. Since the streets connect either 2 $ A$s or 2 $ B$s, then there are $ 2n$ of each type, with $ 4n$ total intersections. But the number of positive and negative intersections are even, so we are done.