The numbers from through 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.
Solution
1. Base Case:
- For , the numbers are .
- 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 is .
2. Inductive Step:
- Assume that for numbers on the circle, the number of good pairs is .
- We need to prove that for numbers on the circle, the number of good pairs is .
3. Inductive Hypothesis:
- Suppose there are numbers on the circle, and the number of good pairs is .
4. **Adding the -th Number:**
- Consider the circle with numbers, including the number .
- The pairs that were good for numbers remain good when we add the -th number.
- By the inductive hypothesis, there are good pairs among the numbers excluding .
5. Including the Number 1:
- When we add the number back into the circle, we need to check if it forms any new good pairs.
- The number 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 form a new good pair because they are not neighbors and the arc between them contains only the number , which is smaller than both of them.
6. Conclusion:
- Therefore, by adding the number , we get one additional good pair.
- The total number of good pairs for numbers is .
The final answer is .