$\indent$ For a positive integer $n$, let $S_n$ be the set of bijective functions from $\{1,2,\dots ,n\}$ to itself. For a pair of positive integers $(a,b)$ such that $1 \leq a <b \leq n$, and for a permutation $\sigma \in S_n$, we say the pair $(a,b)$ is expanding for $\sigma$ if $|\sigma (a)- \sigma(b)| \geq |a-b|$ $\indent$ (a) Is it true that for all integers $n > 1$, there exists $\sigma \in S_n$ so that the number of pairs $(a,b)$ that are expanding for permutation $\sigma$ is less than $1000n\sqrt n$ ? $\indent$ (b) Does there exist a positive integer $n>1$ and a permutation $\sigma \in S_n$ so that the number of pairs $(a,b)$ that are expanding for the permutation $\sigma$ is less than $\frac{n\sqrt n}{1000}$?
Problem
Source: Izho Day 2 Problem 6
Tags: permutation, function, inequalities
Assassino9931
15.01.2025 14:25
Bringing up a discussion on solving this probabilistically. Unfortunately, a direct expected value method does not work (or I have made some serious blunder somewhere) - I get a roughtly $\frac{7}{48}n^2$ bound, which is really bad. By the way, it makes sense that any (constructive or probabilistic) solution which works for a) also works for b) (for large $n$), but it turns out this is far not true...
Pick a permutation uniformly at random. The probability that $(a,b)$, $a<b$ is expanding can be computed as follows: each possible value for $\sigma(a)$ occurs with probability $\frac{1}{n}$, then if $\sigma(a) = j$, the possible values for $\sigma(b)$ are from $b-a + j$ to $n$, as well as from $1$ to $j - (b-a)$, each occuring with probability $\frac{1}{n}$. Hence this probability is $$\frac{1}{n}\left(\sum_{j=1}^{b-a} \frac{n-(b-a+j)+1}{n} + \sum_{j=b-a+1}^{n-b+a} \frac{n - (b - a + j) + 1 + j - (b-a)}{n} + \sum_{j=n-b+a+1}^n \frac{j-(b-a)}{n}\right)$$
Ok, this technically is for $b-a \leq \frac{n}{2}$, I guess a similar calculation would be from $b-a > \frac{n}{2}$, and with a significantly smaller contribution. Anyway, summing the above for the valid $a$ and $b$ gives at most $\frac{7}{48}n^2$ expanding pairs, which is too bad.
Tintarn
15.01.2025 16:42
Yes.
Choose a parameter $1 \le k \le n$ and perform the following: We move every $k$-th number away (say, to the end of the whole thing) and let everything else drop down as far as possible. So for instance $1,2,\dots,k-1$ stay fixed, $k+1,\dots,2k-1$ move one to the left etc.
This way, two numbers in different of these blocks of length $k-1$ cannot form an expanding pair.
Thus, the number of expanding pairs can be bounded (up to rounding errors) by $ \ll \frac{n}{k} \cdot n+\frac{n}{k} \cdot k^2=\frac{n^2}{k}+nk$, where the first term accounts for the pairs involving the multiples of $k$ and the second term accounts for the pairs of numbers in the same block.
To get the optimal bound, we should choose $k \approx \sqrt{n}$, ending up with a bound $O(n^{3/2})$ (and working out all the rounding errors precisely, it is cleat that the constant $1000$ is more than enough.)