
Problem 5. Let $n$ be a positive integer and fix $2 n$ distinct points on a circumference. Split these points into $n$ pairs and join the points in each pair by an arrow (i.e., an oriented line segment). The resulting configuration is good if no two arrows cross, and there are no arrows $\overrightarrow{A B}$ and $\overrightarrow{C D}$ such that $A B C D$ is a convex quadrangle oriented clockwise. Determine the number of good configurations.

Fedor Petrov, Russia


Solution 1. The required number is $\binom{2 n}{n}$. To prove this, trace the circumference counterclockwise to label the points $a_{1}, a_{2}, \ldots, a_{2 n}$.

Let $\mathcal{C}$ be any good configuration and let $O(\mathcal{C})$ be the set of all points from which arrows emerge. We claim that every $n$-element subset $S$ of $\left\{a_{1}, \ldots, a_{2 n}\right\}$ is an $O$-image of a unique good configuration; clearly, this provides the answer.

To prove the claim induct on $n$. The base case $n=1$ is clear. For the induction step, consider any $n$-element subset $S$ of $\left\{a_{1}, \ldots, a_{2 n}\right\}$, and assume that $S=O(\mathcal{C})$ for some good configuration $\mathcal{C}$. Take any index $k$ such that $a_{k} \in S$ and $a_{k+1} \notin S$ (assume throughout that indices are cyclic modulo $2 n$, i.e., $a_{2 n+1}=a_{1}$ etc.).

If the arrow from $a_{k}$ points to some $a_{\ell}, k+1<\ell(<2 n+k)$, then the arrow pointing to $a_{k+1}$ emerges from some $a_{m}, m$ in the range $k+2$ through $\ell-1$, since these two arrows do not cross. Then the arrows $a_{k} \rightarrow a_{\ell}$ and $a_{m} \rightarrow a_{k+1}$ form a prohibited quadrangle. Hence, $\mathcal{C}$ contains an arrow $a_{k} \rightarrow a_{k+1}$.

On the other hand, if any configuration $\mathcal{C}$ contains the arrow $a_{k} \rightarrow a_{k+1}$, then this arrow cannot cross other arrows, neither can it occur in prohibited quadrangles.

Thus, removing the points $a_{k}, a_{k+1}$ from $\left\{a_{1}, \ldots, a_{2 n}\right\}$ and the point $a_{k}$ from $S$, we may apply the induction hypothesis to find a unique good configuration $\mathcal{C}^{\prime}$ on $2 n-2$ points compatible with the new set of sources (i.e., points from which arrows emerge). Adjunction of the arrow $a_{k} \rightarrow a_{k+1}$ to $\mathcal{C}^{\prime}$ yields a unique good configuration on $2 n$ points, as required.
