Maths Olympiad Prep

Library / /114 of 128

Combinatorics Difficulty 6.7 National Olympiad Prove it Philippines

Problem:

Let nn be a positive integer. The numbers 1,2,3,,2n1, 2, 3, \ldots, 2n are randomly assigned to 2n2n distinct points on a circle. To each chord joining two of these points, a value is assigned equal to the absolute value of the difference between the assigned numbers at its endpoints.

Show that one can choose nn pairwise non-intersecting chords such that the sum of the values assigned to them is n2n^{2}.

Solution

Solution:

First, observe that
i=1ni=n(n+1)2andi=n+12ni=n2+n(n+1)2 \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad \text{and} \quad \sum_{i=n+1}^{2n} i = n^{2} + \frac{n(n+1)}{2}
which means that
i=n+12nii=1ni=n2 \sum_{i=n+1}^{2n} i - \sum_{i=1}^{n} i = n^{2}
Let A={1,2,,n}A = \{1, 2, \ldots, n\} and B={n+1,n+2,,2n}B = \{n+1, n+2, \ldots, 2n\}. (Here, we do not distinguish the point labeled xx and the number xx itself.) Because the numbers are arranged on a circle, one can find a pair {x1,y1}\{x_{1}, y_{1}\}, where x1Ax_{1} \in A and y1By_{1} \in B, such that one arc joining x1x_{1} and y1y_{1} contains no other labeled points. One can then remove the chord (including x1x_{1} and y1y_{1}) joining these points. Among the remaining labeled points, one can find again a pair {x2,y2}\{x_{2}, y_{2}\}, where x2A{x1}x_{2} \in A \setminus \{x_{1}\} and y2B{y1}y_{2} \in B \setminus \{y_{1}\}, such that one arc joining x2x_{2} and y2y_{2} does not contain a labeled point, and then remove again the chord (including the endpoints) joining x2x_{2} and y2y_{2}. Continuing this process, one can find pairs {x3,y3},{x4,y4}\{x_{3}, y_{3}\}, \{x_{4}, y_{4}\}, and so on, and then remove the chords joining the pairs.

We claim that the removed chords satisfy the required properties. Clearly, there are nn such chords. Because no labeled point lies on one arc joining xjx_{j} and yjy_{j} for any 1jn1 \leq j \leq n, the removed chords are non-intersecting. Finally, the sum of the values assigned to the removed chords is
j=1n(yjxj)=j=1nyjj=1nxj=i=n+12nii=1ni=n2 \sum_{j=1}^{n} (y_{j} - x_{j}) = \sum_{j=1}^{n} y_{j} - \sum_{j=1}^{n} x_{j} = \sum_{i=n+1}^{2n} i - \sum_{i=1}^{n} i = n^{2}
This ends the proof of our claim.

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.