Let be a set of 16 points in the plane, no three collinear. Let denote the number of ways to draw 8 line segments with endpoints in , such that no two drawn segments intersect, even at endpoints. Find the smallest possible value of across all such .
Solution
The answer is 1430. In general, we prove that with points the answer is the Catalan number .
First of all, it is well-known that if is a convex -gon, then .
It remains to prove the lower bound. We proceed by (strong) induction on , with the base case and clear. Suppose the statement is proven for and consider a set with points.
Let be a point on the convex hull of , and label the other points in order of angle from .
Consider drawing a segment . This splits the remaining points into two halves and , with and points respectively.

Note that by choice of , no segment in can intersect a segment in . By the inductive hypothesis,
Thus, drawing , we have at least ways to complete the drawing. Over all choices of , we obtain
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.