Maths Olympiad Prep

Library / /44 of 46

Geometry Difficulty 7.6 National olympiad, round 2 Prove it Russia

2N2N points are marked on a circle (NN is a positive integer) so that no point in the interior of the circle belongs to three chords with the endpoints at marked points. A collection of NN chords with the endpoints at marked points is called a matching if every marked point is the endpoint of exactly one of these chords. A matching is called even if the number of intersection points of its chords is even, and odd otherwise. Find the difference between the quantities of even and odd matchings.

На окружности отмечено 2N2N точек (NN — натуральное число). Известно, что через любую точку внутри окружности проходит не более двух хорд с концами в отмеченных точках. Назовем паросочетанием такой набор из NN хорд с концами в отмеченных точках, что каждая отмеченная точка является концом ровно одной из этих хорд. Назовём паросочетание чётным, если количество точек, в которых пересекаются его хорды, чётно, и нечётным иначе. Найдите разность между количеством чётных и нечётных паросочетаний.

Solution

Answer. 11.

First solution. By induction on NN, we prove that the number of even matchings is one more than the number of odd matchings. For N=1N=1 the statement is obvious: there is only one matching, and it is even. Now, prove the statement for 2N2N points, assuming it is true for 2(N1)2(N-1) points. Denote the marked points A1,A2,,A2NA_1, A_2, \dots, A_{2N} in order around the circle clockwise.

Lemma. Suppose a matching contains the chord A1AiA_1A_i. Then for even ii it intersects an even number of chords, and for odd ii — an odd number.
Proof. Suppose the chord A1AiA_1A_i is intersected by exactly kk chords. Consider the points A2,,Ai1A_2, \dots, A_{i-1}; exactly kk of them are endpoints of chords intersecting A1AiA_1A_i (one endpoint for each such chord). The remaining i2ki-2-k points are split into pairs of points joined by chords that do not intersect A1AiA_1A_i. Thus, the number i2ki-2-k is even, so ii and kk have the same parity. The lemma is proved. \square

Now, divide all matchings into 2N12N-1 groups Π2,,Π2N\Pi_2, \dots, \Pi_{2N}: group Πi\Pi_i contains those matchings in which point A1A_1 is joined to AiA_i. Now, remove the chord A1AiA_1A_i from each matching in Πi\Pi_i; we get all possible matchings on the remaining 2N22N-2 points. By the induction hypothesis, among them, the number of even matchings is one more than the number of odd matchings. Moreover, if ii is even, then by the lemma the parity of the matching does not change when removing the chord, and if ii is odd, it does change. Thus, in each of the NN sets Π2,,Π2N\Pi_2, \dots, \Pi_{2N}, the number of even matchings is one more than the number of odd, and in each of the N1N-1 sets Π3,,Π2N1\Pi_3, \dots, \Pi_{2N-1}, the number of odd matchings is one more than the number of even. In total, the number of even matchings exceeds the number of odd by N(N1)=1N-(N-1)=1, as required.

Second solution. We give another proof of the induction step.
Let the marked points be A1,,A2NA_1, \dots, A_{2N}. Consider all matchings in which A2N1A_{2N-1} and A2NA_{2N} are joined by a chord. This chord does not intersect any other. Thus, removing it from each such matching, we obtain all matchings on the points A1,,A2N2A_1, \dots, A_{2N-2}, and the parity of each is preserved.

By the induction hypothesis, among these matchings, the number of even is one more than the number of odd.
To complete the proof, it suffices to show that among all other matchings, the numbers of even and odd are equal. Consider any such matching; suppose it contains chords A2N1AiA_{2N-1}A_i and A2NAkA_{2N}A_k. Now "swap" the points A2N1A_{2N-1} and A2NA_{2N}, i.e., replace these chords with A2NAiA_{2N}A_i and A2N1AkA_{2N-1}A_k. If the original chord intersected some of the others, so does the new chord. On the other hand, if the chords A2N1AiA_{2N-1}A_i and A2NAkA_{2N}A_k did not intersect, the new chords will intersect, and vice versa. Thus, to each remaining even matching we associate an odd one, and vice versa; and different matchings correspond to different ones. Therefore, the numbers of even and odd matchings among the rest are equal, as required.

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 and solution reproduced as published; topic and difficulty added by this site.