Maths Olympiad Prep

Library / /74 of 92

Geometry Difficulty 7.1 National olympiad, round 2 Prove it Iran

nn is a positive integer. Let A,BA, B be two sets of nn points in the plane such that no three points of them are collinear. Denote by T(A)T(A) the number of non-self-intersecting broken lines containing n1n-1 segments such that its vertices are in AA. Define T(B)T(B) similarly. If the elements of BB are the vertices of a convex nn-gon but the elements of AA are not, prove that T(B)<T(A)T(B) < T(A).

Solution

We call such a broken line a good path.

Lemma. Let CC be a set of n2n \ge 2 points in the plane, no three of which are collinear and let x0x_0 be a vertex of the convex hull of CC. The number of good paths with vertices of CC starting at x0x_0 is at least 2n22^{n-2}. Equality holds only when CC is convex.

Proof. We use induction on nn. For n=2n=2 it is trivial. Suppose the claim is true for n1n-1. Let x0yx_0y be a line such that C{x0}C - \{x_0\} is entirely in one side of it. Sort the vertices of C{x0}C - \{x_0\} as x1,x2,,xn1x_1, x_2, \dots, x_{n-1} such that the angles xix0y\angle x_i x_0 y are increasing. So C{x0,x1}C - \{x_0, x_1\} is entirely in one side of x0x1x_0x_1 and C{x0,xn1}C - \{x_0, x_{n-1}\} is entirely in one side of x0xn1x_0x_{n-1}. There are at least 2×2n32 \times 2^{n-3} good paths with vertices of C{x0}C - \{x_0\} starting at either x1x_1 or xn1x_{n-1}. By joining the segments x0x1x_0x_1 or x0xn1x_0x_{n-1} we obtain at least 2n22^{n-2} good paths with the vertices of CC starting at x0x_0.

If CC is convex, then in any good path starting at x0x_0, x0x_0 should be joined to x1x_1 or xn1x_{n-1}, because in other cases the vertices will be in both sides of the first segment and the path will intersect the first segment. So equality for convex sets follows by the induction hypothesis.

Now, suppose CC is not convex. Let zz be a vertex of CC not on the convex hull. Either zz is in triangle x0x1xn1x_0x_1x_{n-1} or is inside the convex hull of C{x0}C - \{x_0\} (depending on which side of x1xn1x_1x_{n-1} that zz is in). In the first case, if zz' is the farthest vertex from line in triangle x0x1xn1x_0x_1x_{n-1} (other than x0x_0), then the segment x0zx_0z' doesn't intersect the convex hull of C{x0}C - \{x_0\} and there is a good path starting with x0zx_0z' by the induction hypothesis. In the second case, C{x0}C - \{x_0\} is not convex and the number of good paths starting with x0x1x_0x_1 is more than 2n32^{n-3} by the induction hypothesis. So the lemma is proved. \Box

According to the lemma, we have T(B)=n2n3T(B) = n2^{n-3}. We prove T(A)>n2n3T(A) > n2^{n-3}. Let x0x_0 be a vertex on the convex hull of AA and sort the other vertices of AA as described in the lemma. For any 1in21 \le i \le n-2, by joining any two good paths starting at x0x_0 with vertices of {x0,x1,,xi}\{x_0, x_1, \dots, x_i\} and {x0,xi+1,,xn1}\{x_0, x_{i+1}, \dots, x_{n-1}\}, we get a good path with the vertices of AA, because the two sets can be divided by a line through x0x_0. This way we get i=1n22i1×2ni2=(n2)2n3\sum_{i=1}^{n-2} 2^{i-1} \times 2^{n-i-2} = (n-2)2^{n-3} good vertices not starting at x0x_0. There are more than 2n22^{n-2} good vertices starting at x0x_0 and so T(A)>n2n3T(A) > n2^{n-3}. So, the assertion is proved. \Box

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.