Maths Olympiad Prep

Library / /221 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

The numbers from 11 through 100100 are written in some order on a circle.
We call a pair of numbers on the circle good if the two numbers are not neighbors on the circle and if at least one of the two arcs they determine on the circle only contains numbers smaller then both of them. What may be the total number of good pairs on the circle.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Base Case:
- For n=3 n = 3 , the numbers are 1,2,3 1, 2, 3 .
- We need to check if there are any good pairs.
- A good pair is defined as a pair of numbers that are not neighbors and at least one of the arcs they determine contains only numbers smaller than both of them.
- In this case, there are no such pairs because any pair of numbers will be neighbors on the circle.
- Therefore, the number of good pairs for n=3 n = 3 is 0 0 .

2. Inductive Step:
- Assume that for n n numbers on the circle, the number of good pairs is n3 n - 3 .
- We need to prove that for n+1 n + 1 numbers on the circle, the number of good pairs is (n+1)3=n2 (n + 1) - 3 = n - 2 .

3. Inductive Hypothesis:
- Suppose there are n n numbers on the circle, and the number of good pairs is n3 n - 3 .

4. **Adding the (n+1) (n+1) -th Number:**
- Consider the circle with n+1 n + 1 numbers, including the number 1 1 .
- The pairs that were good for n n numbers remain good when we add the (n+1) (n+1) -th number.
- By the inductive hypothesis, there are n3 n - 3 good pairs among the n n numbers excluding 1 1 .

5. Including the Number 1:
- When we add the number 1 1 back into the circle, we need to check if it forms any new good pairs.
- The number 1 1 cannot form a good pair with any other number because it is the smallest number and cannot satisfy the condition that at least one of the arcs contains only numbers smaller than both of them.
- However, the two neighbors of 1 1 form a new good pair because they are not neighbors and the arc between them contains only the number 1 1 , which is smaller than both of them.

6. Conclusion:
- Therefore, by adding the number 1 1 , we get one additional good pair.
- The total number of good pairs for n+1 n + 1 numbers is n3+1=n2 n - 3 + 1 = n - 2 .

The final answer is n2 \boxed{ n - 2 } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.