Maths Olympiad Prep

Library / /3 of 5

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

There are 20172017 lines in a plane such that no 33 of them go through the same point. Turbo the snail can slide along the lines in the following fashion: she initially moves on one of the lines and continues moving on a given line until she reaches an intersection of 22 lines. At the intersection, she follows her journey on the other line turning left or right, alternating the direction she chooses at each intersection point she passes. Can it happen that she slides through a line segment for a second time in her journey but in the opposite direction as she did for the first time?

Solutions — 4

Solution 1

Solution:

We show that this is not possible.
The lines divide the plane into disjoint regions. We claim that there exists an alternating 22-coloring of these regions, that is each region can be colored in black or white, such that if two regions share a line segment, they have a different color. We show this inductively.
If there are no lines, this is obvious. Consider now an arrangement of nn lines in the plane and an alternating 22-coloring of the regions. If we add a line gg, we can simply switch the colors of all regions in one of the half planes divided by gg from white to black and vice versa. Any line segment not in gg will still be between two regions of different color. Any line segment in gg cuts a region determined by the nn lines in two, and since we switched colors on one side of gg this segment will also lie between two regions of different color.
Now without loss of generality we may assume, that Turbo starts on a line segment with a white region on her left and a black one on her right. At any intersection, if she turns right, she will keep the black tile to her right. If she turns left, she will keep the white tile to her left. Thus wherever she goes, she will always have a white tile on her left and a black tile on her right. As a consequence, she can cross every line segment only in the direction where she has a white tile to her left, and never the opposite direction where she would have a black tile to the left.

Solution 2

Solution:

Suppose the assumption is true.
Let's label each segment in the snail's path with L\mathbf{L} or R\mathbf{R} depending on the direction that Turbo chose at the start point of this segment (one segment can have several labels if it has been visited several times).
Consider the first segment that has been visited twice in different directions, name this segment s1s_{1}. Assume without loss of generality that it is labeled with L\mathbf{L}. Then next segment must be labeled with R\mathbf{R}, name this one s2s_{2}.
Let's look at the label which s1s_{1} can get on the second visit. If it gets L\mathbf{L} then the previous segment in the path must be s2s_{2}. But in this case s1s_{1} is not the first segment that has been visited twice in different directions because s2s_{2} has been visited earlier. So the second label of s1s_{1} must be R\mathbf{R}, and Turbo must have come from the opposite side of s2s_{2}.

Figure 1

Since Turbo alters directions at each point, labels in her path also alter. And because two labels of s1s_{1} are different, the number of visited segments between these two visits must be even.
Now let's make the following observation: each segment in the path corresponds to exactly one line, and its previous and next segments are on opposite sides of this line.

Figure 2

Again consider the path between two visits of s1s_{1}.
Each line intersecting this path must be crossed an even number of times because Turbo has to return to the initial side of each line. Therefore, an even number of segments of Turbo's path are contained on each of these lines. But the line containing s1s_{1} must be crossed an odd number times. Since each crossing corresponds to exactly one segment in the path, the number of segments must be odd.
Here we get the contradiction. Therefore, the assumption is false.

Solution 3

Solution:

Suppose that the snail always slides slightly to the right of the line segments on her path. When turning to the right, she does not cross any line, whereas when turning to the left, she crosses exactly two lines. This means that at any time of her journey, she has crossed an even number of lines.
Assuming that at some point she slides along a segment for the second time, but in the opposite direction, we argue that she needs to cross an odd number of lines. Let \ell be the line on which the revisit happens. In order to get to the other side of \ell, the snail has to cross \ell an odd number of times. To visit the same segment of \ell, she must cross every other line an even number of times.

Solution 4

Solution:

Let us color in red all intersection points of the given lines and let us choose one of two possible directions on each segment (draw an arrow on each segment). Consider a red point RR where two given lines aa and bb meet, and the four segments a1,a2,b1,b2a_{1}, a_{2}, b_{1}, b_{2} with endpoint RR (so that aia,bjba_{i} \subset a, b_{j} \subset b). RR is called a saddle if on a1,a2a_{1}, a_{2} the arrows go out of RR while on b1,b2b_{1}, b_{2} the arrows enter RR, or vice versa, on b1,b2b_{1}, b_{2} the arrows go out of RR while on a1,a2a_{1}, a_{2} the arrows enter RR. The set of arrows (chosen on all segments) is said to be good if all red points are saddles. It is sufficient to prove that there exists a good set of arrows. Indeed, if initially Turbo is moving along (or opposite) the arrow, then this condition holds after she turns at a red point.
The given lines cut the plane into regions. Further we need the following property of the good set of arrows (this property directly follows from the definition): the boundary of any bounded region is a directed cycle of arrows; the boundary of any unbounded region is a directed chain of arrows.
We construct a good set of arrows by induction on nn with trivial base n=1n=1. Now erase one of nn given lines and assume we have a good set of arrows for remaining n1n-1 lines. Now restore the nn-th line \ell, assume that \ell is horizontal. Denote by A1,,An1A_{1}, \ldots, A_{n-1} all new red points on \ell from the left to the right. Each of AiA_{i} belongs to some old segment mim_{i} of the line i\ell_{i}. Let us call AiA_{i} ascending if the arrow on mim_{i} goes up, and descending if the arrow on mim_{i} goes down. Consider the region containing the segment AiAi+1A_{i}A_{i+1}. By the property, AiA_{i} and Ai+1A_{i+1} can not be both ascending or both descending. Thus we can choose arrows on all pieces of \ell so that each arrow goes from a descending to an ascending vertex.
Each of points AiA_{i} cuts mim_{i} into two new pieces; the direction of new pieces supposed to be the same as on mim_{i}. Now simultaneously change the direction of arrows on all pieces below the line \ell. It is easy to see that A1,,An1A_{1}, \ldots, A_{n-1} become saddles, while the other red points remain saddles. This completes the induction step.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.