Maths Olympiad Prep

Library /

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Romania

Let nn be a positive integer and fix 2n2n distinct points on a circumference. Split these points into nn 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 AB\overrightarrow{AB} and CD\overrightarrow{CD} such that ABCDABCD is a convex quadrangle oriented clockwise. Determine the number of good configurations.

Solution

First solution. The required number is (2nn)\binom{2n}{n}. To prove this, trace the circumference counterclockwise to label the points a1,a2,,a2na_1, a_2, \dots, a_{2n}.
Let C\mathcal{C} be any good configuration and let O(C)O(\mathcal{C}) be the set of all points from which arrows emerge. We claim that every nn-element subset SS of {a1,,a2n}\{a_1, \dots, a_{2n}\} is an OO-image of a unique good configuration; clearly, this provides the answer.
To prove the claim induct on nn. The base case n=1n=1 is clear. For the induction step, consider any nn-element subset SS of {a1,,a2n}\{a_1, \dots, a_{2n}\}, and assume that S=O(C)S = O(\mathcal{C}) for some good configuration C\mathcal{C}. Take any index kk such that akSa_k \in S and ak+1Sa_{k+1} \notin S (assume throughout that indices are cyclic modulo 2n2n, i.e., a2n+1=a1a_{2n+1} = a_1 etc.).
If the arrow from aka_k points to some aa_\ell, k+1<<(2n+k)k+1 < \ell < (2n+k), then the arrow pointing to ak+1a_{k+1} emerges from some ama_m, mm in the range k+2k+2 through 1\ell-1, since these two arrows do not cross. Then the arrows akaa_k \to a_\ell and amak+1a_m \to a_{k+1} form a prohibited quadrangle. Hence, C\mathcal{C} contains an arrow akak+1a_k \to a_{k+1}.
On the other hand, if any configuration C\mathcal{C} contains the arrow akak+1a_k \to a_{k+1}, then this arrow cannot cross other arrows, neither can it occur in prohibited quadrangles.
Thus, removing the points ak,ak+1a_k, a_{k+1} from {a1,,a2n}\{a_1, \dots, a_{2n}\} and the point aka_k from SS, we may apply the induction hypothesis to find a unique good configuration C\mathcal{C}' on 2n22n-2 points compatible with the new set of sources (i.e., points from which arrows emerge). Adjunction of the arrow akak+1a_k \to a_{k+1} to C\mathcal{C}' yields a unique good configuration on 2n2n points, as required.

Second solution. Use the counterclockwise labeling a1,a2,,a2na_1, a_2, \dots, a_{2n} in the solution above.
Letting DnD_n be the number of good configurations on 2n2n points, we establish a recurrence relation for the DnD_n. To this end, let Cn=(2n)!n!(n+1)!C_n = \frac{(2n)!}{n!(n+1)!} the nnth Catalan number; it is well-known that CnC_n is the number of ways to connect 2n2n given points on the circumference by nn pairwise disjoint chords.
Since no two arrows cross, in any good configuration the vertex a1a_1 is connected to some a2ka_{2k}. Fix kk in the range 11 through nn and count the number of good configurations containing the arrow a1a2ka_1 \to a_{2k}. Let C\mathcal{C} be any such configuration.
In C\mathcal{C}, the vertices a2,,a2k1a_2, \dots, a_{2k-1} are paired off with one other, each arrow pointing from the smaller to the larger index, for otherwise it would form a prohibited quadrangle with a1a2ka_1 \to a_{2k}. Consequently, there are Ck1C_{k-1} ways of drawing such arrows between a2,,a2k1a_2, \dots, a_{2k-1}.
On the other hand, the arrows between a2k+1,,a2na_{2k+1}, \dots, a_{2n} also form a good configuration, which can be chosen in DnkD_{n-k} ways. Finally, it is easily seen that any configuration of the first kind and any configuration of the second kind combine together to yield an overall good configuration.
Thus the number of good configurations containing the arrow a1a2ka_1 \to a_{2k} is Ck1DnkC_{k-1}D_{n-k}. Clearly, this is also the number of good configurations containing the arrow a2(nk+1)a1a_{2(n-k+1)} \to a_1, so
Dn=2k=1nCk1Dnk.() D_n = 2 \sum_{k=1}^{n} C_{k-1} D_{n-k}. \quad (*)
To find an explicit formula for DnD_n, let d(x)=n=0Dnxnd(x) = \sum_{n=0}^{\infty} D_n x^n and let c(x)=n=0Cnxn=114x2xc(x) = \sum_{n=0}^{\infty} C_n x^n = \frac{1-\sqrt{1-4x}}{2x} be the generating functions of the DnD_n and the CnC_n, respectively. Since D0=1D_0 = 1, relation (*) yields d(x)=2xc(x)d(x)+1d(x) = 2xc(x)d(x) + 1, so
d(x)=112xc(x)=(14x)1/2=n0(12)(32)(2n12)(4x)nn!=n02n(2n1)!!n!xn=n0(2nn)xn. d(x) = \frac{1}{1 - 2xc(x)} = (1 - 4x)^{-1/2} = \sum_{n \ge 0} \left(-\frac{1}{2}\right) \left(-\frac{3}{2}\right) \cdots \left(-\frac{2n-1}{2}\right) \frac{(-4x)^n}{n!} \\ = \sum_{n \ge 0} \frac{2^n(2n-1)!!}{n!} x^n = \sum_{n \ge 0} \binom{2n}{n} x^n.
Consequently, Dn=(2nn)D_n = \binom{2n}{n}.

Third solution. Let Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n} denote the nnth Catalan number and recall that there are exactly CnC_n ways to join 2n2n distinct points on a circumference by nn pairwise disjoint chords. Such a configuration of chords will be referred to as a *Catalan nn-configuration*. An orientation of the chords in a Catalan configuration CC making it into a good configuration (in the sense defined in the statement of the problem) will be referred to as a good orientation for CC.
We show by induction on nn that there are exactly n+1n+1 good orientations for any Catalan nn-configuration, so there are exactly (n+1)Cn=(2nn)(n+1)C_n = \binom{2n}{n} good configurations on 2n2n points. The base case n=1n=1 is clear.
For the induction step, let n>1n > 1, let CC be a Catalan nn-configuration, and let abab be a chord of minimal length in CC. By minimality, the endpoints of the other chords in CC all lie on the major arc abab of the circumference.
Label the 2n2n endpoints 1, 2, ..., 2n2n counterclockwise so that {a,b}={1,2}\{a, b\} = \{1, 2\}, and notice that the good orientations for CC fall into two disjoint classes: Those containing the arrow 121 \to 2, and those containing the opposite arrow.
Since the arrow 121 \to 2 cannot be involved in a prohibited quadrangle, the induction hypothesis applies to the Catalan (n1)(n-1)-configuration formed by the other chords to show that the first class contains exactly nn good orientations.
Finally, the second class consists of a single orientation, namely, 212 \to 1, every other arrow emerging from the smaller endpoint of the respective chord; a routine verification shows that this is indeed a good orientation. This completes the induction step and ends the proof.

Fourth solution. (Sang-il Oum) As in the previous solution, we intend to count the number of good orientations of a Catalan nn-configuration.
For each such configuration, we consider its dual graph TT whose vertices are finite regions bounded by chords and the circle, and an edge connects two regions sharing a boundary segment. This graph TT is a plane tree with nn edges and n+1n+1 vertices. There is a canonical bijection between orientations of chords and orientations of edges of TT in such a way that each chord crosses an edge of TT from the right to the left of the arrow on that edge. A good orientation of chords corresponds to an orientation of the tree containing no two edges oriented towards each other. Such an orientation is defined uniquely by its source vertex, i.e., the unique vertex having no incoming arrows.
Therefore, for each tree TT on n+1n+1 vertices, there are exactly n+1n+1 ways to orient it so that the source vertex is unique — one for each choice of the source. The answer now follows along the lines in the solution above.

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.