Suppose there are $n\geq{5}$ different points arbitrarily arranged on a circle, the labels are $1, 2,\dots $, and $n$, and the permutation is $S$. For a permutation , a “descending chain” refers to several consecutive points on the circle , and its labels is a clockwise descending sequence (the length of sequence is at least $2$), and the descending chain cannot be extended to longer .The point with the largest label in the chain is called the "starting point of descent", and the other points in the chain are called the “non-starting point of descent” . For example: there are two descending chains $5, 2$and $4, 1$ in $5, 2, 4, 1, 3$ arranged in a clockwise direction, and $5$ and $4$ are their starting points of descent respectively, and $2, 1$ is the non-starting point of descent . Consider the following operations: in the first round, find all descending chains in the permutation $S$, delete all non-starting points of descent , and then repeat the first round of operations for the arrangement of the remaining points, until no more descending chains can be found. Let $G(S)$ be the number of all descending chains that permutation $S$ has appeared in the operations, $A(S)$ be the average value of $G(S)$of all possible n-point permutations $S$. (1) Find $A(5)$. (2)For $n\ge{6}$ , prove that $\frac{83}{120}n-\frac{1}{2} \le A(S) \le \frac{101}{120}n-\frac{1}{2}.$
Problem
Source: 2021China South East Mathematical Olympiad
Tags: combinatorics, Sequence
sarjinius
24.10.2021 11:20
Define $S(n) = A(1) + A(2) + \dots + A(n)$.
For each permutation $S$, we separate it into two sequences of clockwise consecutive integers $S_1$ and $S_2$, whose starting points are $n$ and $n-1$ respectively. Note that $S_1$ or $S_2$ can be one integer long.
We call one of $S_1$ or $S_2$ completely reduced if all numbers other than its starting point are removed.
Since the largest number is the starting point for both $S_1$ and $S_2$, the total number of descending chains in $S_1$ and $S_2$ is $G(S_1)$ and $G(S_2)$ respectively.
If $S_1$ is completely reduced before $S_2$ is completely reduced, then at the time $S_1$ is completely reduced, $n-1$ is to the right of $n$, and since $S_2$ is not yet completely reduced, $n$ will just attach itself to the descending chain that includes $n-1$. Essentially, $n$ replaces $n-1$ as the starting point of $S_2$ until it is completely reduced. Thus, in this case, $G(S)=G(S_1)+G(S_2)$.
If $S_2$ is completely reduced before $S_1$ is completely reduced, then at the time $S_2$ is completely reduced, $n-1$ is to the left of $n$, and since all other numbers are less than $n-1$, $n-1$ will not be a part of a descending chain until $S_1$ is completely reduced. Then only $n$ and $n-1$ remain on the circle, which form the last descending chain. Thus, in this case, $G(S)=G(S_1)+G(S_2)+1$.
If $S_1$ and $S_2$ are completely reduced simultaneously, then when both of them are completely reduced, only $n$ and $n-1$ remain, which form the last descending chain. Thus, in this case, $G(S)=G(S_1)+G(S_2)+1$.
For each permutation $S$, let $S’$ be the permutation formed when $n$ and $n-1$ are swapped.
If $S_1$ is first to completely reduce in $S$, then $S_2$ is first to completely reduce in $S’$ and vice versa.
If $S_1$ and $S_2$ completely reduce simultaneously in $S$, then they completely reduce simultaneously in $S’$ as well.
For each permutation $S$, if $S_1$ and $S_2$ completely reduce simultaneously, then $\frac{G(S_1)+G(S_2)}{2}=G(S_1)+G(S_2)+1$.
Otherwise, $\frac{G(S_1)+G(S_2)}{2}=G(S_1)+G(S_2)+\frac{1}{2}$.
Note that $S_1$ can be any permutation of length $i$ such that $i=1,2,\dots,n-1$, and $S_2$ can be any permutation of length $n-i$.
Note that $\frac{G(S_1)+G(S_2)}{2} \ge G(S_1)+G(S_2)+\frac{1}{2}$. Taking the average of both sides, we get $$A(n) \ge \frac{1}{n-1} \sum_{i=1}^{n-1} (A(i)+A(n-i)) + \frac{1}{2} = \frac{2S(n-1)}{n-1} + \frac{1}{2}.$$If $n$ and $n-1$ are next to each other, then it is impossible for $S_1$ and $S_2$ to completely reduce simultaneously. There is a $\frac{1}{n-1}$ chance that $n-1$ will be next to $n$, so there is at least a $\frac{1}{n-1}$ chance that $\frac{G(S_1)+G(S_2)}{2} \ge G(S_1)+G(S_2)+\frac{1}{2}$ and at most a $\frac{n-2}{n-1}$ chance that $\frac{G(S_1)+G(S_2)}{2} \ge G(S_1)+G(S_2)+1$.
We get $$A(n) \le \frac{1}{n-1} \sum_{i=1}^{n-1} (A(i)+A(n-i)) + \frac{n-2}{n-1} + \frac{1}{2} \cdot \frac{1}{n-1} = \frac{2S(n-1)}{n-1} + \frac{2n-3}{2n-2}.$$Thus, $$\frac{2S(n-1)}{n-1} + \frac{1}{2} \le A(n) \le \frac{2S(n-1)}{n-1} + \frac{2n-3}{2n-2}.$$Adding $S(n-1)$ to all three sides, we get
$$\frac{(n+1)S(n-1)}{n-1} + \frac{1}{2} \le S(n) \le \frac{(n+1)S(n-1)}{n-1} + \frac{2n-3}{2n-2},$$which can be rearranged to get
$$S(n) + \frac{n}{2} \ge \frac{n+1}{n-1}\left(S(n-1) + \frac{n-1}{2}\right)$$and
$$S(n)+n-\frac{1}{4} \le \frac{n+1}{n-1}\left(S(n-1)+(n-1)-\frac{1}{4}\right)$$Let $X_n = S(n) + \frac{n}{2}$ and $Y_n = S(n) + n - \frac{1}{4}$.
So we have
$$X_n \ge \frac{n+1}{n-1}X_{n-1} \iff \frac{X_n}{X_{n-1}} \ge \frac{n+1}{n-1} \implies \frac{X_n}{X_k} = \frac{X_n}{X_{n-1}} \cdot \frac{X_{n-1}}{X_{n-2}} \cdot \ldots \cdot \frac{X_{k+1}}{X_k}$$$$\ge \frac{n+1}{n-1} \cdot \frac{n}{n-2} \cdot \ldots \cdot \frac{k+2}{k} = \frac{n(n+1)}{k(k+1)} \iff X_n \ge \frac{n(n+1)}{k(k+1)}X_k$$$$S(n) + \frac{n}{2} \ge \frac{n(n+1)}{k(k+1)}\left(S(k) + \frac{k}{2} \right)$$for all integers $k \ge 2$.
Similarly, we also have
$$Y_n \le \frac{n(n+1)}{k(k+1)}Y_k$$$$S(n) + n - \frac{1}{4} \le \frac{n(n+1)}{k(k+1)}\left(S(k) + k - \frac{1}{4} \right)$$for all integers $k \ge 2$.
Next, we find the value of $S(5)$.
It is easy to see that $A(1) = 0, A(2) = 1, A(3) = \frac{3}{2}, A(4) = \frac{7}{3}$.
To get $A(5)$, we calculate the number of descending chains in each of the $24$ permutations. Assume that $5$ is the first term in each of those permutations.
$5, 4, 3, 2, 1 \to 5$ --- $1$ descending chain
$5, 4, 3, 1, 2 \to 5, 2 \to 5$ --- $2$ descending chains
$5, 4, 2, 3, 1 \to 5, 3 \to 5$ --- $3$ descending chains
$5, 4, 2, 1, 3 \to 5, 3 \to 5$ --- $2$ descending chains
$5, 4, 1, 3, 2 \to 5, 3 \to 5$ --- $3$ descending chains
$5, 4, 1, 2, 3 \to 5, 2, 3 \to 5, 3 \to 5$ --- $3$ descending chains
$5, 3, 4, 2, 1 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 3, 4, 1, 2 \to 5, 4, 2 \to 5$ --- $3$ descending chains
$5, 3, 2, 4, 1 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 3, 2, 1, 4 \to 5, 4 \to 5$ --- $2$ descending chains
$5, 3, 1, 4, 2 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 3, 1, 2, 4 \to 5, 2, 4 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 2, 4, 3, 1 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 2, 4, 1, 3 \to 5, 4, 3 \to 5$ --- $3$ descending chains
$5, 2, 3, 4, 1 \to 5, 3, 4 \to 5, 4 \to 5$ --- $4$ descending chains
$5, 2, 3, 1, 4 \to 5, 3, 4 \to 5, 4 \to 5$ --- $4$ descending chains
$5, 2, 1, 4, 3 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 2, 1, 3, 4 \to 5, 3, 4 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 1, 4, 3, 2 \to 5, 4 \to 5$ --- $3$ descending chains
$5, 1, 4, 2, 3 \to 5, 4, 3 \to 5$ --- $3$ descending chains
$5, 1, 3, 4, 2 \to 5, 3, 4 \to 5, 4 \to 5$ --- $4$ descending chains
$5, 1, 3, 2, 4 \to 5, 3, 4 \to 5, 4 \to 5$ --- $4$ descending chains
$5, 1, 2, 4, 3 \to 5, 2, 4 \to 5, 4 \to 5$ --- $4$ descending chains
$5, 1, 2, 3, 4 \to 5, 2, 3, 4 \to 5, 3, 4 \to 5, 4 \to 5$ --- $4$ descending chains
There are a total of $73$ descending chains in $24$ permutations, thus, $\boxed{A(5) = \frac{73}{24}}$. Also, $S(5) = A(1) + A(2) + A(3) + A(4) + A(5) = 1 + \frac{3}{2} + \frac{7}{3} + \frac{73}{24} = \frac{63}{8}$.
Plugging $k=5$ and $n \to n-1$ into $S(n) + \frac{n}{2} \ge \frac{n(n+1)}{k(k+1)}\left(S(k) + \frac{k}{2} \right)$, we get
$$S(n-1) \ge \frac{n(n-1)}{30}\left(\frac{63}{8} + \frac{5}{2}\right) - \frac{n-1}{2} = (n-1)\left(\frac{83n}{240} - \frac{1}{2}\right).$$Plugging this into $A(n) \ge \frac{2S(n-1)}{n-1} + \frac{1}{2}$, we get
$$A(n) \ge \frac{83n}{120}-1+\frac{1}{2} = \frac{83n}{120}-\frac{1}{2}.$$
Plugging $k=5$ and $n \to n-1$ into $S(n) + n - \frac{1}{4} \le \frac{n(n+1)}{k(k+1)}\left(S(k) + k - \frac{1}{4} \right)$, we get
$$S(n-1) \le \frac{n(n-1)}{30}\left(\frac{63}{8}+5-\frac{1}{4}\right)-(n-1)+\frac{1}{4}=(n-1)\left(\frac{101n}{240}-1\right)+\frac{1}{4}.$$Plugging this into $A(n) \le \frac{2S(n-1)}{n-1} + \frac{2n-3}{2n-2}$, we get
$$A(n) \le \frac{101n}{120} - 2 + \frac{1}{2n-2} + \frac{2n-3}{2n-2} = \frac{101n}{120} - 1 < \frac{101n}{120} - \frac{1}{2}.$$Therefore, $\frac{83n}{120}-\frac{1}{2} \le A(n) \le \frac{101n}{120} - \frac{1}{2}$.