Olympiad Maths Prep

Track / Stage 7 / 239 of 300 #1639 of 2000

Problem 1639

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.6 Prove it

There are nn distinct points on a circumference. Choose one of the points. Connect this point and the mmth point from the chosen point counterclockwise with a segment. Connect this mmth point and the mmth point from this mmth point counterclockwise with a segment. Repeat such steps until no new segment is constructed. From the intersections of the segments, let the number of the intersections - which are in the circle - be II. Answer the following questions (mm and nn are positive integers that are relatively prime and they satisfy 62m<n6 \leq 2m < n).

1) When the nn points take different positions, express the maximum value of II in terms of mm and nn.

2) Prove that InI \geq n. Prove that there is a case, which is I=nI=n, when m=3m=3 and nn is arbitrary even number that satisfies the condition.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

### Part 1: Maximum Value of I I

1. Understanding the Problem:
- We have n n distinct points on a circumference.
- We connect each point to the m m -th point counterclockwise.
- We continue this process until no new segment is constructed.
- We need to find the maximum number of intersections I I inside the circle.

2. Counting Intersections:
- Each segment can intersect with other segments.
- For each of the n n diagonals, there are 2(m1) 2(m-1) potential intersection points with other diagonals.
- Each intersection point is counted twice (once for each segment involved in the intersection).

3. Maximum Intersections:
- The maximum number of intersections I I can be given by:
I(m1)n I \leq (m-1)n
- This is because each of the n n diagonals can intersect with 2(m1) 2(m-1) other diagonals.

### Part 2: Proving In I \geq n

1. Injection Argument:
- Consider each diagonal AiAi+m A_iA_{i+m} .
- For each diagonal, consider the point of intersection between it and Ai+m1Ai+2m1 A_{i+m-1}A_{i+2m-1} .
- This gives an injection from the set of n n diagonals to the set of intersection points I I .

2. Conclusion:
- Since there is an injection from the set of n n diagonals to I I , we have:
In I \geq n

### Special Case: m=3 m = 3 and n n is an Even Number

1. Construction:
- Start with a regular n2 \frac{n}{2} -gon X0,X2,,Xn2 X_0, X_2, \ldots, X_{n-2} .
- Take X1,X3,,Xn1 X_1, X_3, \ldots, X_{n-1} to be the midpoints of X0X2,X2X4,,Xn2X0 X_0X_2, X_2X_4, \ldots, X_{n-2}X_0 respectively.
- Define Ak=XkXk+2Xk+3Xk+5 A_k = X_kX_{k+2} \cap X_{k+3}X_{k+5} for all k{0,1,,n1} k \in \{0, 1, \ldots, n-1\} (indices modulo n n ).

2. Verification:
- This construction ensures that each diagonal intersects exactly once with another diagonal.
- Therefore, the number of intersections I I is exactly n n .

The final answer is I=(m1)n \boxed{ I = (m-1)n } and In I \geq n with I=n I = n for m=3 m = 3 and n n even.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.