Let $\mathcal{S}$ be a set of 16 points in the plane, no three collinear. Let $\chi(\mathcal{S})$ denote the number of ways to draw 8 line segments with endpoints in $\mathcal{S}$, such that no two drawn segments intersect, even at endpoints. Find the smallest possible value of $\chi(\mathcal{S})$ across all such $\mathcal{S}$.
The answer is 1430 . In general, we prove that with $2 n$ points the answer is the $n^{\text {th }}$ Catalan number $C_{n}=\frac{1}{n+1}\binom{2 n}{n}$.

First of all, it is well-known that if $\mathcal{S}$ is a convex $2 n$-gon, then $\chi(\mathcal{S})=C_{n}$.
It remains to prove the lower bound. We proceed by (strong) induction on $n$, with the base case $n=0$ and $n=1$ clear. Suppose the statement is proven for $0,1, \ldots, n$ and consider a set $\mathcal{S}$ with $2(n+1)$ points.

Let $P$ be a point on the convex hull of $\mathcal{S}$, and label the other $2 n+1$ points $A_{1}, \ldots, A_{2 n+1}$ in order of angle from $P$.
Consider drawing a segment $\overline{P A_{2 k+1}}$. This splits the $2 n$ remaining points into two halves $\mathcal{U}$ and $\mathcal{V}$, with $2 k$ and $2(n-k)$ points respectively.

Note that by choice of $P$, no segment in $\mathcal{U}$ can intersect a segment in $\mathcal{V}$. By the inductive hypothesis,
$$
\chi(\mathcal{U}) \geq C_{k} \quad \text { and } \quad \chi(\mathcal{V}) \geq C_{n-k} .
$$

Thus, drawing $\overline{P A_{2 k+1}}$, we have at least $C_{k} C_{n-k}$ ways to complete the drawing. Over all choices of $k$, we obtain
$$
\chi(\mathcal{S}) \geq C_{0} C_{n}+\cdots+C_{n} C_{0}=C_{n+1}
$$
as desired.
Remark. It is possible to show directly from the lower bound proof that convex $2 n$-gons achieve the minimum: indeed, every inequality is sharp, and no segment $\overline{P A_{2 k}}$ can be drawn (since this splits the rest of the points into two halves with an odd number of points, and no crossing segment can be drawn).
Bobby Shen points out that in the case of 6 points, a regular pentagon with its center also achieves equality, so this is not the only equality case.

Remark. The result that $\chi(S) \geq 1$ for all $S$ is known (consider the choice of 8 segments with smallest sum), and appeared on Putnam 1979. However, it does not seem that knowing this gives an advantage for this problem, since the answer is much larger than 1 .