Problem: 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}$.

Solution: The answer is $1430$.
In general, we prove that with $2n$ points
the answer is the $n$\ts{th} Catalan number
$C_n = \tfrac{1}{n+1}\tbinom{2n}{n}$.

First of all, it is well-known that if $\mathcal{S}$ is a convex $2n$-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, \dots, 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 $2n+1$ points $A_1, \dots, A_{2n+1}$
in order of angle from $P$.

Consider drawing a segment $\ol{PA_{2k+1}}$.
This splits the $2n$ remaining points
into two halves $\mathcal{U}$ and $\mathcal{V}$,
with $2k$ and $2(n-k)$ points respectively.

\begin{center}
\begin{asy}
  unitsize(50);
  pair P = (0, 0);
  pair[] A = {2*dir(200), 1.7*dir(215), 2.5*dir(230), 1.8*dir(240), 1.6*dir(260), 2.3*dir(275), 2.4*dir(285), 1.7*dir(295), 2.2*dir(310), 2.2*dir(330), 1.9*dir(345)};
  dot(P);
  for (int i = 0; i < A.length; ++i) dot(A[i]);
  draw(P--A[4]);
  draw(A[4]--(3*A[4]-2*P), dashed);

  label("$P$", P, dir(90));
  for (int i = 0; i < A.length; ++i) label("$A_{" + string(i+1) + "}$", A[i], dir(A[i]));
  clip(box((-2.5, -3), (2.5, 2)));
\end{asy}
\end{center}

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}) \ge C_k \quad \text{and} \quad \chi(\mathcal{V}) \ge C_{n-k}.\]
Thus, drawing $\ol{PA_{2k+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}) \ge C_0 C_n + \dots + C_n C_0 = C_{n+1}\]
as desired.

\begin{remark*}
  It is possible to show directly from the lower bound proof
  that convex $2n$-gons achieve the minimum:
  indeed, every inequality is sharp,
  and no segment $\ol{PA_{2k}}$ 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.
\end{remark*}

\begin{remark*}
  The result that $\chi(S) \ge 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$.
\end{remark*}