Maths Olympiad Prep

Library / /4 of 73

Combinatorics Difficulty 7.5 National Olympiad, round 2 Prove it Turkey

2022 points of a circle are uniformly marked (arc distances between neighbouring marked points coincide). kk arcs with different lengths and with endpoints at marked points are chosen so that no arc lies inside another one. Find the largest possible value of kk.

Solution

Answer: 1011.
We show that the answer for 2n2n points is nn. Let us numerate marked points in clockwise order by 1,2,,2n1, 2, \dots, 2n. The arc starting at point aa and ending at bb in clockwise order will be denoted by [a,b][a, b].

The nn arcs chosen as [1,2],[2,4],[3,6],[4,8],,[n1,2n2],[n,2n][1, 2], [2, 4], [3, 6], [4, 8], \dots, [n-1, 2n-2], [n, 2n] satisfy conditions.

Now suppose that kn+1k \ge n+1 chosen arcs satisfy problem conditions. Let the shortest and longest chosen arcs are [a,b][a, b] and [c,d][c, d], respectively. Suppose that the arc lengths of [a,b][a, b] and [c,d][c, d] are ll and mm, respectively.

Case 1. [a,b][c,d]=[a, b] \cap [c, d] = \emptyset.
Any chosen arc except [a,b][a, b] and [c,d][c, d] will either start on arc [a+1,c1][a+1, c-1] or end on arc [d+1,b1][d+1, b-1]. Internal marked points of [a,b][a, b] can be both starting and ending points of chosen arcs. Therefore, the sum of the number of possible starting and ending points is t=2n(m+1)+(l1)t = 2n - (m+1) + (l-1). Since ml+nm \ge l+n we get tn2t \le n-2. There are at least n1n-1 chosen arcs except [a,b][a, b] and [c,d][c, d]. Each of them either starts or ends at one of these n2n-2 points. Therefore, two of these arcs either starts or ends at the same marked point, a contradiction.

Case 2. [a,b][c,d][a, b] \cap [c, d] \neq \emptyset. Without loss of generality a(c,d]a \in (c, d].
Any chosen arc except [a,b][a, b] and [c,d][c, d] will either will start on arc [a+1,c1][a+1, c-1] or end on arc [d+1,b1][d+1, b-1]. Let kk be the length of arc [d,b][d, b]. Internal marked points of [d,b][d, b] can be both starting and ending points of chosen arcs. Therefore, the sum of the number of possible starting and ending points is t=2n(m+1)+(l1)t = 2n - (m+1) + (l-1). Since ml+nm \ge l+n we get tn2t \le n-2. There are at least n1n-1 chosen arcs except [a,b][a, b] and [c,d][c, d]. Each of them either starts or ends at one of these n2n-2 points. Therefore, two of these arcs either starts or ends at the same marked point, a contradiction. Done.

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.