Maths Olympiad Prep

Library / /17 of 19

Combinatorics Difficulty 8.6 Shortlist Find the answer

For any permutation pp of set {1,2,,n}\{1, 2, \ldots, n\}, define d(p)=p(1)1+p(2)2++p(n)nd(p) = |p(1) - 1| + |p(2) - 2| + \ldots + |p(n) - n|. Denoted by i(p)i(p) the number of integer pairs (i,j)(i, j) in permutation pp such that 1<jn1 \leqq < j \leq n and p(i)>p(j)p(i) > p(j). Find all the real numbers cc, such that the inequality i(p)cd(p)i(p) \leq c \cdot d(p) holds for any positive integer nn and any permutation p.p.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to understand the relationship between d(p)d(p) and i(p)i(p) for any permutation pp of the set {1,2,,n}\{1, 2, \ldots, n\}.

### Definitions:
- A permutation pp of a set {1,2,,n}\{1, 2, \ldots, n\} is a bijection from the set to itself. For simplicity, represent the permutation as a sequence (p(1),p(2),,p(n))(p(1), p(2), \ldots, p(n)).
- The function d(p)d(p) is defined as:
d(p)=p(1)1+p(2)2++p(n)n. d(p) = |p(1) - 1| + |p(2) - 2| + \ldots + |p(n) - n|.
d(p)d(p) measures how far the permutation is from the identity permutation, with each term being the absolute difference between the position and its value.
- The function i(p)i(p), known as the inversion count, is the number of pairs (i,j) (i, j) such that 1i<jn 1 \leq i < j \leq n and p(i)>p(j) p(i) > p(j) .

### Objective:
Find all real numbers cc such that for any permutation pp of {1,2,,n}\{1, 2, \ldots, n\}, the inequality i(p)cd(p)i(p) \leq c \cdot d(p) holds.

### Exploration:
To find the relationship and determine possible values of cc, evaluate special cases of permutations:

1. Identity permutation: p(i)=ip(i) = i for all ii.
- Here, d(p)=0d(p) = 0 and i(p)=0i(p) = 0. The inequality i(p)cd(p)i(p) \leq c \cdot d(p) holds trivially.

2. Simple transpositions:
- Consider a permutation where only two elements are swapped: p=(1  n)p = (1 \; n).
- In this case, p(1)=np(1) = n and p(n)=1p(n) = 1. Thus:
d(p)=n1+1n+i=2n10=2(n1). d(p) = |n - 1| + |1 - n| + \sum_{i=2}^{n-1} 0 = 2(n - 1).
- Since nn being at position 1 and 1 being at position nn forms an inversion, i(p)=1i(p) = 1.
- For the inequality to hold:
1c2(n1)    c12(n1). 1 \leq c \cdot 2(n - 1) \implies c \geq \frac{1}{2(n - 1)}.

### General Consideration:
Evaluating different permutations by increasing the complexity, a pattern emerges where permutations near identity tend to have fewer inversions and a smaller d(p)d(p), whereas permutations with many transpositions have a larger d(p)d(p) with potentially many inversions.

### Conclusion:
The critical evaluation at this stage indicates that the inequality i(p)cd(p)i(p) \leq c \cdot d(p) primarily depends on the nature of inversions, which can be controlled and minimized relative to d(p)d(p) with correct scaling. Therefore, the required condition might be stringent, limiting possible values of cc from becoming arbitrary.

However, for practical nn and permutation pp, minimal conditions suggest that relative inversion versus distance tends to zero unless a non-trivial scaling satisfies:
c1 c \geq 1

Thus, upon considering permutations with substantial urbanization away from identity, the method confirms:

c=1 \boxed{c = 1}
This result establishes a generic boundary through practical permutation assessments and satisfies the condition imposed by observing transformations in sequence order.

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