Shmarov V.

On a circle, $2 N$ points are marked ($N$ is a natural number). It is known that through any point inside the circle, no more than two chords with endpoints at the marked points pass. We will call a matching a set of $N$ chords with endpoints at the marked points such that each marked point is the endpoint of exactly one of these chords. We will call a matching even if the number of points where its chords intersect is even, and odd otherwise. Find the difference between the number of even and odd matchings.
Let the marked points be $A_{1}, A_{2}, \ldots, A_{2 N}$ in the order of clockwise traversal of the circle. We will prove by induction on $N$ that the number of even matchings is one more than the number of odd matchings. For $N=1$, the statement is obvious: there is only one matching, and it is even.

Inductive step. First method. Suppose in the matching there is a chord $A_{1} A_{i}$ and it is intersected by exactly $k$ chords.

Consider the points $A_{2}, \ldots, A_{i-1}$; exactly $k$ of them are endpoints of chords intersecting $A_{1} A_{i}$. The remaining $i-2-k$ points are paired by chords that do not intersect $A_{1} A_{i}$. Thus, the number $i-2-k$ is even, meaning that the numbers $i$ and $k$ have the same parity.

We divide all matchings into $2 N-1$ groups $\Pi_{2}, \ldots, \Pi_{2 N}$: the group $\Pi_{i}$ will contain those matchings in which point $A_{1}$ is connected to $A_{i}$. Remove the chord $A_{1} A_{i}$ from each matching in $\Pi_{i}$; we will get all possible matchings on the remaining $2 N-2$ points. By the inductive hypothesis, among them, there are one more even matchings than odd ones. If $i$ is even, the parity of the matching does not change upon removal, and if $i$ is odd, it changes. Therefore, in each of the $N$ sets $\Pi_{2}, \ldots, \Pi_{2 N}$, there are one more even matchings than odd ones, and in each of the $N-1$ sets $\Pi_{3}, \ldots, \Pi_{2 N-1}$, there are one more odd matchings than even ones. In total, there are one more even matchings than odd ones, $N-(N-1)=1$.

Second method. Consider all matchings in which $A_{2 N-1}$ and $A_{2 N}$ are connected by a chord. This chord does not intersect any other. Therefore, by removing it from each of the considered matchings, we will get all matchings on the points $A_{1}, \ldots, A_{2 N-2}$, and the parity of each of them will be preserved. By the inductive hypothesis, among our matchings, there are one more even matchings than odd ones.

It remains to prove that among the remaining matchings, there are an equal number of even and odd ones. Consider any of them; suppose it contains chords $A_{2 N-1} A_{i}$ and $A_{2 N} A_{k}$. Replace these chords with $A_{2 N} A_{i}$ and $A_{2 N-1} A_{k}$. In this case, if the original chord intersected with some other, then the new chord will also intersect with it. On the other hand, if the chords $A_{2 N-1} A_{i}$ and $A_{2 N} A_{k}$ did not intersect, then the new chords will intersect, and vice versa. Thus, we have divided the remaining matchings into pairs of different parities.

## Answer

1. 

Submit a comment