Maths Olympiad Prep

Library / /18 of 18

Geometry Difficulty 7.8 National olympiad, round 2 Prove it Austria

Alice and Bob play a game, in which they take turns drawing segments of length 11 in the Euclidean plane. Alice begins, drawing the first segment, and from then on, each segment must start at the endpoint of the previous segment. It is not permitted to draw the segment lying over the preceding one. If the new segment shares at least one point—except for its starting point—with one of the previously drawn segments, one has lost.

a) Show that both Alice and Bob could force the game to end, if they don't care who wins.

b) Is there a winning strategy for one of them?

(Michael Reitmeir)

Solution

a) In the following, let AnA_n denote the end-point of the segment that Alice drew in her nn-th turn (assuming the game has not ended by then), and let BnB_n denote the end-point of Bob's nn-th segment. Furthermore, let B0B_0 denote the starting point of Bob's first segment.
If Alice can force an end to the game, so can Bob by applying the same strategy and ignoring Alice's first move. It is therefore sufficient to prove that Alice can force an end.
Bob must always choose the nn-th end-point BnB_n on the circle with radius 11 and center in AnA_n. We name this circle knk_n. Furthermore, let lnl_n denote the line perpendicular to Bn1AnB_{n-1}A_n through AnA_n. We now note that if Bob chooses his end-point in such a way that his segment forms an acute angle with the preceding segment (such that BnB_n lies on the same side of lnl_n as the segment Bn1An\overline{B_{n-1}A_n}), Alice can end the game with her next move. Now let hnh_n denote the part of knk_n on the opposite side of lnl_n from Bn1An\overline{B_{n-1}A_n} (including the intersection points of lnl_n and knk_n). In the following, we only need to consider the case in which Bob chooses the point BnB_n on the semi-circle hnh_n.
Let BB denote the set of all points, whose distance from the first drawn segment is less than 11. The set BB consists of a 1×21 \times 2 rectangle and the interior of two semi-circles. Bob chooses B1B_1 on h1h_1. In the next move, Alice can choose A2A_2 as close as she wishes to A1A_1. Let rr denote the distance between A2A_2 and A1A_1. We now consider two cases.

Case 1: B0,A1,B1B_0, A_1, B_1 do not lie on a common line.
Figure 1

If Alice chooses A2=A1A_2 = A_1 (which she is not allowed to do, according to the rules), h2h_2 will overlap with the semicircular edge of BB at one end. The other end of h2h_2 must therefore lie in the interior of the rectangular section of BB, which means that this end must have a positive distance from the edge of BB. Since Alice can choose an arbitrarily small value of rr, she can (for reasons of continuity) move the point A2A_2 away slightly from A1A_1 towards the rectangular section of BB such that h2h_2 comes to lie completely in the interior of BB. This means that B2B_2 will lie completely in the interior of BB, and all its points thus have a distance less than 11 from the first segment. Alice can therefore certainly choose her next segment in such a way that it intersects the first segment.

Figure 1

Figure 2

Case 2: B0,A1,B1B_0, A_1, B_1 lie on a common line.
In this case, Alice cannot choose A2A_2 in such a way that h2h_2 lies completely in the interior of BB. If Bob chooses B2B_2 in the interior of BB, Alice can choose her next segment in such a way that it intersects the first segment, ending the game. We can therefore assume that Bob chooses B2B_2 on h2h_2 outside of BB. In this case, Alice can choose her next point A3A_3 in such a way that its distance from A2A_2 is at most rr. By the triangle inequality, the distance from A3A_3 to A1A_1 is then at most 2r2r. If r=0r = 0 (which is not allowed by the rules), we would have A3=A1A_3 = A_1. In this case, analogously to the previous case, h3h_3 would overlap with the semicircular edge of BB, and the other end would lie in the interior of the rectangular part of BB with a positive distance from the edge. Since Alice can choose 2r2r arbitrarily small, she can (again by reasons of continuity) move A3A_3 slightly away from A1A_1 toward the part of h3h_3 in the interior of the rectangular section of BB, such that h3h_3 comes to lie completely in the interior of BB. Then B3B_3 lies in the interior of BB, and Alice can choose her next segment in such a way that it intersects the first segment.

b) We will show that each of the players can always make a move with which they do not lose. This is trivially the case for the first two moves, so we assume without loss of generality that at least two segments have already been drawn. Let ss denote the last segment drawn and tt the one drawn immediately before that. Furthermore, let SS denote the union of all segments that were drawn before ss and tt. Let rr denote the smallest distance between any of the points of ss and SS. Since ss and SS are assumed to not have any common points, we certainly have r>0r > 0.
Figure 3

Now let BB denote the set of all points xx, whose distance from ss is less than r/2r/2. BB certainly does not contain any point from SS. The only segments among those that have been drawn to this point that contain any of the points in BB are thus ss and tt. Extending ss to a line, we divide the Euclidean plane into two half-planes, one of which certainly does not include any of the points of tt. We choose this half-plane and determine its intersection with BB. We can certainly find a segment of length 11 in this part of BB, with one end in the end of ss, that does not intersect either tt or any of the other segments.

Figure 3

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 and solution reproduced as published; topic and difficulty added by this site.