In a certain city there are $n$ straight streets, such that every two streets intersect, and no three streets pass through the same intersection. The City Council wants to organize the city by designating the main and the side street on every intersection. Prove that this can be done in such way that if one goes along one of the streets, from its beginning to its end, the intersections where this street is the main street, and the ones where it is not, will apear in alternating order. Proposed by Serbia
Problem
Source:
Tags: combinatorics
cadaeibf
12.09.2020 18:56
It is known that we can color the different regions the straight line the divide the plane in with two colours, such that no two neighbouring regions have the same colors. So If a region is black we go around it in counterclockwise order, and each time we meet another street, we go left and choose the new street as the main Street for that crossing. We do a similar thing for white, except by going in clockwise direction. Now if one follows a straight line since the colours on the right alternate, it also follows that the main and non-main streets alternate
dgrozev
26.05.2023 17:02
We prove that a greedy algorithm works. We pick up a street and assign alternating traffic signs at each intersection on this street, from the first intersection to the last one. Then we mark the street. After that, we pick up another street, and start placing signs from some intersection of this street with an already marked street, and so on. Assume that the street $\ell_0$ is the first street for which it is impossible to do this procedure because there is a conflict of traffic signs. This means that starting from an intersection $X$ of $\ell_0,$ that has already a sign assigned, and placing signs, we reach an intersection $Y$ which already has a set sign and it conflicts the sign we are going to place. Let $X=\ell_0\cap \ell_1, Y=\ell_0\cap \ell_2.$ Thus, $\ell_1$ and $\ell_2$ have been marked without any conflicts. Let $Z:=\ell_1\cap\ell_2.$ Clearly, our conflict at the point $Y$ can only happen if the number of intersections on $\ell_1$ between $X$ and $Z$ (without these points) plus the number of intersections on $\ell_2$ between $Z$ and $Y$ has a different parity than the number of intersections on $\ell_0$ between $X$ and $Y.$ This would mean that the number of intersections on the triangle $XYZ$ (not counting $X,Y,Z$) is odd. Let us now see why it is impossible. Note that any line that intersects a side of the triangle $XYZ$ in an interior point, also intersects another side of this triangle in an interior point. That is, each line either doesn't intersect the triangle or intersects exactly two of its sides. That's why the number of the intersections on $X,Y,Z$ (not counting the vertices) is even. So, this way no conflict is possible and we can set up all the traffic signs as needed.