10.4. 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.

(V. Shmarov)
Answer. 1.

First solution. We will prove by induction on $N$ that there is one more even matching than odd. For $N=1$, the statement is obvious: there is only one matching, and it is even. Now we will prove the statement for $2N$ points, assuming it is true for $2(N-1)$ points. Let the marked points be $A_{1}, A_{2}, \ldots, A_{2N}$ in the order of traversal of the circle clockwise.

Lemma. Suppose a chord $A_{1}A_{i}$ is involved in the matching. Then for even $i$, it intersects an even number of chords, and for odd $i$, an odd number.

Proof. Let the chord $A_{1}A_{i}$ intersect exactly $k$ chords. Consider the points $A_{2}, \ldots, A_{i-1}$; exactly $k$ of them are the endpoints of chords intersecting $A_{1}A_{i}$ (one endpoint of each chord). The remaining $i-2-k$ points are paired with points connected 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. The lemma is proved.

Now we will divide all matchings into $2N-1$ groups $\Pi_{2}, \ldots, \Pi_{2N}$: the group $\Pi_{i}$ will contain those matchings in which point $A_{1}$ is connected to $A_{i}$. Now, remove the chord $A_{1}A_{i}$ from each matching in $\Pi_{i}$; we will get all possible matchings on the remaining $2N-2$ points. By the induction hypothesis, among them, there is one more even matching than odd. At the same time, if $i$ is even, then according to the lemma, the parity of the matching does not change when removed, and if $i$ is odd, it changes. Thus, in each of the $N$ sets $\Pi_{2}, \ldots, \Pi_{2N}$, there is one more even matching than odd, and in each of the $N-1$ sets $\Pi_{3}, \ldots, \Pi_{2N-1}$, there is one more odd than even. In total, there are more even matchings than odd by $N-(N-1)=1$, which is what we needed to prove.

Second solution. We will provide another proof of the induction step.

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

To complete the proof, it is sufficient to show that among all other matchings, there are equally many even and odd. Consider any of them; suppose it contains chords $A_{2N-1}A_{i}$ and $A_{2N}A_{k}$. Now, "swap" the points $A_{2N-1}$ and $A_{2N}$, that is, replace the chords with $A_{2N}A_{i}$ and $A_{2N-1}A_{k}$. In this case, if the original chord intersected with some of the others, then the new chord will also intersect with it. On the other hand, if the chords $A_{2N-1}A_{i}$ and $A_{2N}A_{k}$ did not intersect, then the new chords will intersect, and vice versa. Thus, to each remaining even matching, we have associated an odd one, and vice versa; different matchings, obviously, correspond to different ones. Therefore, there are equally many remaining even and odd matchings, which is what we needed to prove.