A windmill is a closed line segment of unit length with a distinguished endpoint, the pivot. Let $S$ be a finite set of $n$ points such that the distance between any two points of $S$ is greater than $c$. A configuration of $n$ windmills is admissible if no two windmills intersect and each point of $S$ is used exactly once as a pivot. An admissible configuration of windmills is initially given to Geoff in the plane. In one operation Geoff can rotate any windmill around its pivot, either clockwise or counterclockwise and by any amount, as long as no two windmills intersect during the process. Show that Geoff can reach any other admissible configuration in finitely many operations, where (i) $c = \sqrt 3$, (ii) $c = \sqrt 2$. Proposed by Michael Ren
Problem
Source: ELMO 2018 #6, 2018 ELMO SL C3
Tags: combinatorics
28.06.2018 13:14
28.06.2018 17:42
I am posting the official solution: Throughout the solution we will general denote pivots by $P$, $Q$, $R$, \dots and non-pivots by $A$, $B$, $C$, \dots We say that a configuration of windmills around $S$ is admissible if no two windmills intersect. The problem is equivalent to showing one can reach any admissible configuration from any other (and the final position with the windmills pointing the same direction is just one example of a clearly admissible configuration). Draw a red line segment between any two pivots which have distance at most $2$ (thus these windmills could intersect). This naturally gives us a graph $\mathcal{G}$. Lemma: For $c \ge \sqrt 2$, the graph $\mathcal{G}$ is planar. Proof. Indeed, if $\overline{PA}$ and $\overline{QB}$ intersect, we can consider convex quadrilateral $PQAB$, one of whose angles is at least $90^\circ$. WLOG it is $\angle PQA$, in which case $PA^2 \ge PQ^2 + QA^2 > 2+2 = 4$, so $\overline{PA}$ should not be red. $\blacksquare$ [asy][asy] size(8cm); pair P = (0,0); pair X = 1.83 * dir(95); pair Y = 1.89 * dir(35); pair Z = 2.40 * dir(-10); pair W = 1.87 * dir(-60); pair J = 1.85 * dir(170); pair A = X+1.87*dir(80); pair B = Y+1.80*dir(50); pair C = Z+1.83*dir(-15); pair D = A+1.64*dir(5); pair E = B+1.85*dir(-20); pair F = E+1.95*dir(-55); pair G = E+1.65*dir(80); real c = 2**0.5; pair[] S = {P,X,Y,Z,W,J,A,B,C,D,E,F,G}; for (int i=0; i<S.length-1; ++i) { for (int j=i+1; j<S.length; ++j) { assert(abs(S[i]-S[j]) > c, "sad"); if (abs(S[i]-S[j]) < 2) draw(S[i]--S[j], red+linewidth(0.3)); } } real[] theta = {60, 330, 289, 32, 144, 50, 300, 250, 210, 260, 240, 170, 135}; for (int i=0; i<theta.length; ++i) { draw(S[i]--(S[i]+dir(theta[i])), grey+linewidth(0.9)); dot(S[i]); } [/asy][/asy] Clearly, we can ignore any isolated vertices. We can also ignore any leaves in $\mathcal{G}$; indeed suppose $P$ is a pivot with $\overline{PQ}$ the only red edge. Then we can rotate the windmill at $P$ to point away from $Q$ and it will never obstruct other windmills since $c \ge 1$, so we can delete the pivot $P$ from consideration (and use induction on the number of pivots, say). Thus, we may assume $\mathcal{G}$ is a finite planar graph with no leaves. Thus it makes sense to speak of the faces of planar graph $\mathcal{G}$, consisting of several polygons. Lemma: A windmill with pivot $P$ can never intersect a red edge other than those touching $P$. Proof. Suppose windmill $\overline{PA}$ intersects red edge $\overline{QR}$. Then the altitude from $\overline{PH}$ to $\overline{QR}$ has length at most $1$. WLOG that $QH < RH$, so $QH < \frac{1}{2} QR = 1$. Then $PQ^2 < QH^2 + HP^2 < 1 + 1 = 2$, contradiction. $\blacksquare$ From now on, a windmill $\overline{PA}$ is said to hug a red edge $\overline{PQ}$ if the angle $\angle QPA < \varepsilon$ for some sufficiently small $\varepsilon$ in terms of $\mathcal{G}$; each red edge $\overline{PQ}$ has at most two windmills hugging it (namely the windmills with pivots $P$ and $Q$; if this happens, the windmills are on opposite sides of $\overline{PQ}$). Call a windmill configuration cuddly if every windmill is hugging an edge. Claim: We can reach some cuddly configuration from any admissible one. Proof. Indeed, consider a windmill $\overline{PA}$ not hugging any edge, and an edge $\overline{PQ}$, and such that $\angle APQ = \theta$ is minimal among all such pairs. Let $\angle RPQ$ be the corresponding angle of the face containing $\overline{PA}$, and let $\overline{QB}$, $\overline{RC}$ be windmills. If $\overline{QB}$ is hugging $\overline{PQ}$, we perturb it slightly so that $A$ and $B$ are on opposite sides of $\overline{PQ}$; thus $\overline{QB}$ is no longer in the way. We rotate $\overline{PA}$ towards $\overline{PQ}$ now. Because we assumed $\theta = \angle APQ$ was minimal, it is impossible for the body of the windmill to collide with the points $B$ or $C$. So the only way it can be obstructed is if the point $A$ collides with the interior of $\overline{QB}$ or $\overline{RC}$. [asy][asy] pair P = origin; pair Q = 1.5*dir(0); pair R = 1.6*dir(130); draw(R--P--Q, red); pair A = dir(30); pair B = Q+dir(A-Q)*dir(-4);; draw(P--A, grey+1.5); draw(Q--B, grey+1.5); pair C = R+dir(-22); draw(R--C, grey+1.5); label("$\theta$", P, 5*dir(A+Q)); dot("$P$", P, dir(270)); dot("$Q$", Q, dir(270)); dot("$R$", R, dir(130)); dot("$A$", A, dir(-90)); dot("$B$", B, dir(B)); dot("$C$", C, dir(C)); /* TSQ Source: P = origin R270 Q = 1.5*dir(0) R270 R = 1.6*dir(130) R130 R--P--Q red A = dir 30 R-90 B = Q+dir(A-Q)*dir(-4); P--A grey+1.5 Q--B grey+1.5 C = R+dir(-22) R--C grey+1.5 !label("$\theta$", P, 5*dir(A+Q)); */ [/asy][/asy] Suppose that $A$ collided with $\overline{QB}$. At the moment of collision, we would have to have $\angle PAQ \le 90^{\circ}$. (This is because just before the collision $\overline{PA}$ was still disjoint from $\overline{QB}$, and if $\angle PAQ \ge 90^{\circ}$ just before then it would remain disjoint as $\overline{PA}$ rotated.) But then $PQ^2 \le PA^2 + AQ^2 \le 2$, contradiction. A similar proof works for $\overline{RC}$. Thus we can rotate the windmills one by one so they hug the edges, as desired. $\blacksquare$ It remains to show any two cuddly configurations can be reached from each other. For this, we make two observations. Suppose $\overline{PA}$ and $\overline{QB}$ both hug $\overline{PQ}$. We show we can interchange the two. Assume $\angle RPQ$ is the angle of a face containing $A$, and $\angle TPQ$, $\angle PQS$ are the angles of the face containing $B$. [asy][asy] pair P = origin; pair Q = dir(20); pair S = Q+1.05*dir(-20); pair R = 1.1*dir(130); pair T = 0.9*dir(260); pair V = R+0.4*dir(80); pair W = Q+0.5*dir(85); draw(V--R--P--T, red); draw(P--Q--W, red); draw(Q--S, red); pair A = 0.73*dir(Q)*dir(10); pair B = Q+0.68*dir(P-Q)*dir(10); draw(P--A, grey+1.5); draw(Q--B, grey+1.5); dot("$P$", P, dir(315)); dot("$Q$", Q, dir(Q)); dot("$S$", S, dir(S)); dot("$R$", R, dir(R)); dot("$T$", T, dir(T)); dot("$A$", A, dir(A)); dot("$B$", B, dir(270)); /* TSQ Source: P = origin R315 Q = dir 20 S = Q+1.05*dir(-20) R = 1.1*dir(130) T = 0.9*dir(260) V := R+0.4*dir(80) W := Q+0.5*dir(85) V--R--P--T red P--Q--W red Q--S red A = 0.73*dir(Q)*dir(10) B = Q+0.68*dir(P-Q)*dir(10) R270 P--A grey+1.5 Q--B grey+1.5 */ [/asy][/asy] Rotate $\overline{PA}$ so it hugs $\overline{PR}$ (possibly perturbing the windmill at $R$), and then rotate $\overline{QB}$ so it hugs $\overline{QS}$ (possibly perturbing the windmill at $S$). Then rotate $\overline{PA}$ so it hugs $\overline{PT}$, then move $\overline{QB}$ back so it hugs $\overline{PQ}$ from the other side, and rotate $\overline{PA}$ back. Now suppose $\overline{PA}$ hugs $\overline{PQ}$, and $\angle RPQ$ is the angle of a face containing $A$. Then we can rotate it so that $\overline{PA}$ hugs $\overline{PR}$ (here $\overline{PA}$ could be blocked by $\overline{QB}$ initially, but then we perform the switching operation above). Together these two observations finish the problem.
29.06.2018 04:20
An interesting extension is to determine the best possible $c$. The ELMO Jury has shown that $c\ge2\sin36^\circ$, but this does not seem to be tight.
29.06.2018 09:34
I suspect $c=1$ fails, but $c=1+\epsilon$ works.
29.06.2018 22:40
I think reading comprehension is just as important as math ability, if not more. Note that $2\sin 36^{\circ}>1$.
30.06.2018 03:00
adamov1 wrote: I think reading comprehension is just as important as math ability, if not more. My mistake. I somehow missed the $\ge$ sign and interpreted his statement as $c=2\sin 36^{\circ}$ working.