Maths Olympiad Prep

Library / /6 of 34

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Let SS be a set of 16 points in the plane, no three collinear. Let χ(S)\chi(S) denote the number of ways to draw 8 line segments with endpoints in SS, such that no two drawn segments intersect, even at endpoints. Find the smallest possible value of χ(S)\chi(S) across all such SS.

Solution

The answer is 1430. In general, we prove that with 2n2n points the answer is the nthn^{\text{th}} Catalan number Cn=1n+1(2nn)C_n = \frac{1}{n+1}\binom{2n}{n}.
First of all, it is well-known that if SS is a convex 2n2n-gon, then χ(S)=Cn\chi(S) = C_n.

It remains to prove the lower bound. We proceed by (strong) induction on nn, with the base case n=0n=0 and n=1n=1 clear. Suppose the statement is proven for 0,1,,n0, 1, \dots, n and consider a set SS with 2(n+1)2(n+1) points.
Let PP be a point on the convex hull of SS, and label the other 2n+12n+1 points A1,,A2n+1A_1, \dots, A_{2n+1} in order of angle from PP.
Consider drawing a segment PA2k+1\overline{PA_{2k+1}}. This splits the 2n2n remaining points into two halves U\mathcal{U} and V\mathcal{V}, with 2k2k and 2(nk)2(n-k) points respectively.

Figure 1

Note that by choice of PP, no segment in U\mathcal{U} can intersect a segment in V\mathcal{V}. By the inductive hypothesis,
χ(U)Ckandχ(V)Cnk. \chi(\mathcal{U}) \ge C_k \quad \text{and} \quad \chi(\mathcal{V}) \ge C_{n-k}.
Thus, drawing PA2k+1\overline{PA_{2k+1}}, we have at least CkCnkC_k C_{n-k} ways to complete the drawing. Over all choices of kk, we obtain
χ(S)C0Cn++CnC0=Cn+1 \chi(S) \ge C_0 C_n + \dots + C_n C_0 = C_{n+1}
as desired.

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.