Let $p$ be an arbitrary odd prime and $\sigma(n)$ for $1 \le n \le p-1$ denote the inverse of $n \pmod p$. Show that the number of pairs $(a,b) \in \{1,2,\cdots,p-1\}^2$ with $a<b$ but $\sigma(a) > \sigma(b)$ is at least $$\left \lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor$$ usjl Note: Partial credits may be awarded if the $4$ in the statement is replaced with some larger constant
Problem
Source: IMOC 2021 N11
Tags: number theory
USJL
12.08.2021 02:51
I'm pretty proud of this problem I was kind of surprise that I could actually say something about the statistics of this seemingly random permutation. One thing that I could not do by myself is to estimate the length of its LIS or LDS---it looks easier to give a lower bound of the length of LDS, but both seem hard. I'd like to see some nontrivial bound on those two.
quotient8
12.08.2021 17:31
The following solution is inspired by the magical properties of the function $x\mapsto 1-\frac{1}{x}$. Unfortunately, it does not elucidate further structure regarding the permutation $\sigma$.
Note $\sigma: \{1,2,\dots,p-1\}\to \{1,2,\dots,p-1\}$ is a bijection, and thus a permutation. Furthermore, $\sigma(1)=1$, so $\sigma$ may be restricted to a permutation on $\{2,\dots,p-1\}$. In fact, the pairs $(a,b)$ with $a=1$ do not satisfy the question condition, so we may restrict our attention to the domain $\{2,\dots,p-1\}$.
Define $\psi: \{2,\dots,p-1\}\to \{2,\dots,p-1\}$ by $\psi(n) = p+1-\sigma(n)$. One may verify that $\psi^3(n)=n$ for all $2\leq n\leq p-1$ (this is because $f: \mathbb R\setminus\{0,1\}\to \mathbb R\setminus\{0,1\}, x\mapsto 1-\frac{1}{x}$ satisfies $f^3(x) \equiv x$, and one may take mod $p$).
Let $N$ be the number of pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, satisfying \begin{align}
(b-a)(\psi(b)-\psi(a))>0.
\end{align}In english, this means either $a<b$ and $\psi(a)<\psi(b)$, or $a>b$ and $\psi(a)>\psi(b)$.Then $N$ also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi(b)-\psi(a))(\psi^2(b)-\psi^2(a))>0,
\end{align}and also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi^2(b)-\psi^2(a))(b-a)>0.
\end{align}However, for each pair $(a,b)$ with $a\neq b$, at least one of the three equations $(1),(2),(3)$ are satisfied (as the product of all three is positive). By a Double Counting argument, running across all $(p-2)(p-3)$ pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, we get $$N\geq \frac{(p-2)(p-3)}{3}.$$
Finally, we note that for $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, that $$(\sigma(a)-\sigma(b))(\psi(a)-\psi(b))<0.$$
Therefore, the the number of pairs $(a,b) \in \{1,2,\cdots,p-1\}^2$ with $a<b$ but $\sigma(a) > \sigma(b)$ is exactly equal to $$\frac{N}{2}\geq \frac{(p-2)(p-3)}{6}\geq \left\lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor$$where the factor of half arises from WLOG $a<b$. The final inequality may be verified to be true for $p=3$ and $p\geq 5$.
USJL
12.08.2021 17:39
quotient8 wrote: The following solution is inspired by the magical properties of the function $x\mapsto 1-\frac{1}{x}$. Unfortunately, it does not elucidate further structure regarding the permutation $\sigma$.
Note $\sigma: \{1,2,\dots,p-1\}\to \{1,2,\dots,p-1\}$ is a bijection, and thus a permutation. Furthermore, $\sigma(1)=1$, so $\sigma$ may be restricted to a permutation on $\{2,\dots,p-1\}$. In fact, the pairs $(a,b)$ with $a=1$ do not satisfy the question condition, so we may restrict our attention to the domain $\{2,\dots,p-1\}$.
Define $\psi: \{2,\dots,p-1\}\to \{2,\dots,p-1\}$ by $\psi(n) = p+1-\sigma(n)$. One may verify that $\psi^3(n)=n$ for all $2\leq n\leq p-1$ (this is because $f: \mathbb R\setminus\{0,1\}\to \mathbb R\setminus\{0,1\}, x\mapsto 1-\frac{1}{x}$ satisfies $f^3(x) \equiv x$, and one may take mod $p$).
Let $N$ be the number of pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, satisfying \begin{align}
(b-a)(\psi(b)-\psi(a))>0.
\end{align}In english, this means either $a<b$ and $\psi(a)<\psi(b)$, or $a>b$ and $\psi(a)>\psi(b)$.Then $N$ also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi(b)-\psi(a))(\psi^2(b)-\psi^2(a))>0,
\end{align}and also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi^2(b)-\psi^2(a))(b-a)>0.
\end{align}However, for each pair $(a,b)$ with $a\neq b$, at least one of the three equations $(1),(2),(3)$ are satisfied (as the product of all three is positive). By a Double Counting argument, running across all $(p-2)(p-3)$ pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, we get $$N\geq \frac{(p-2)(p-3)}{3}.$$
Finally, we note that for $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, that $$(\sigma(a)-\sigma(b))(\psi(a)-\psi(b))<0.$$
Therefore, the the number of pairs $(a,b) \in \{1,2,\cdots,p-1\}^2$ with $a<b$ but $\sigma(a) > \sigma(b)$ is exactly equal to $$\frac{N}{2}\geq \frac{(p-2)(p-3)}{6}\geq \left\lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor$$where the factor of half arises from WLOG $a<b$. The final inequality may be verified to be true for $p=3$ and $p\geq 5$.
Whoa this is surprising! This idea had never come to me, and this is strictly superior to my method in terms of the leading coefficient. Nice one!
KrazyGuy
18.09.2021 18:33
quotient8 wrote: The following solution is inspired by the magical properties of the function $x\mapsto 1-\frac{1}{x}$. Unfortunately, it does not elucidate further structure regarding the permutation $\sigma$.
Note $\sigma: \{1,2,\dots,p-1\}\to \{1,2,\dots,p-1\}$ is a bijection, and thus a permutation. Furthermore, $\sigma(1)=1$, so $\sigma$ may be restricted to a permutation on $\{2,\dots,p-1\}$. In fact, the pairs $(a,b)$ with $a=1$ do not satisfy the question condition, so we may restrict our attention to the domain $\{2,\dots,p-1\}$.
Define $\psi: \{2,\dots,p-1\}\to \{2,\dots,p-1\}$ by $\psi(n) = p+1-\sigma(n)$. One may verify that $\psi^3(n)=n$ for all $2\leq n\leq p-1$ (this is because $f: \mathbb R\setminus\{0,1\}\to \mathbb R\setminus\{0,1\}, x\mapsto 1-\frac{1}{x}$ satisfies $f^3(x) \equiv x$, and one may take mod $p$).
Let $N$ be the number of pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, satisfying \begin{align}
(b-a)(\psi(b)-\psi(a))>0.
\end{align}In english, this means either $a<b$ and $\psi(a)<\psi(b)$, or $a>b$ and $\psi(a)>\psi(b)$.Then $N$ also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi(b)-\psi(a))(\psi^2(b)-\psi^2(a))>0,
\end{align}and also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi^2(b)-\psi^2(a))(b-a)>0.
\end{align}However, for each pair $(a,b)$ with $a\neq b$, at least one of the three equations $(1),(2),(3)$ are satisfied (as the product of all three is positive). By a Double Counting argument, running across all $(p-2)(p-3)$ pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, we get $$N\geq \frac{(p-2)(p-3)}{3}.$$
Finally, we note that for $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, that $$(\sigma(a)-\sigma(b))(\psi(a)-\psi(b))<0.$$
Therefore, the the number of pairs $(a,b) \in \{1,2,\cdots,p-1\}^2$ with $a<b$ but $\sigma(a) > \sigma(b)$ is exactly equal to $$\frac{N}{2}\geq \frac{(p-2)(p-3)}{6}\geq \left\lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor$$where the factor of half arises from WLOG $a<b$. The final inequality may be verified to be true for $p=3$ and $p\geq 5$.
Brilliant!!
CANBANKAN
13.03.2022 20:17
This solution uses properties about $j-\frac 1j$ and is rather clean. Lemma (ISL1990, SEIF 2022/5): let $\sigma$ be a permutation $[n]\to [n]$. Then $\sum_{k=1}^n |k-\sigma(k)|\le 2I$ where I is the number of inversions of $\sigma$ Proof: induct on I, swap two elements at a time Or count number of numbers smaller than an element with a larger index. Now, we know $j-\frac 1j$ goes through all values $k$ such that $k^2+4$ is a perfect square. There are at least $\frac{p-3}{2}$ such values. Therefore, the sum of all possible values of $j-\frac 1j$ is at least $1+...+\frac{p-3}{4}=\frac{p^2}{8})-O(p)$. The sum that is at most 2I is $\frac{p^2}{8}-O(p)$
aaabc123mathematics
09.05.2022 17:05
quotient8 wrote: The following solution is inspired by the magical properties of the function $x\mapsto 1-\frac{1}{x}$. Unfortunately, it does not elucidate further structure regarding the permutation $\sigma$.
Note $\sigma: \{1,2,\dots,p-1\}\to \{1,2,\dots,p-1\}$ is a bijection, and thus a permutation. Furthermore, $\sigma(1)=1$, so $\sigma$ may be restricted to a permutation on $\{2,\dots,p-1\}$. In fact, the pairs $(a,b)$ with $a=1$ do not satisfy the question condition, so we may restrict our attention to the domain $\{2,\dots,p-1\}$.
Define $\psi: \{2,\dots,p-1\}\to \{2,\dots,p-1\}$ by $\psi(n) = p+1-\sigma(n)$. One may verify that $\psi^3(n)=n$ for all $2\leq n\leq p-1$ (this is because $f: \mathbb R\setminus\{0,1\}\to \mathbb R\setminus\{0,1\}, x\mapsto 1-\frac{1}{x}$ satisfies $f^3(x) \equiv x$, and one may take mod $p$).
Let $N$ be the number of pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, satisfying \begin{align}
(b-a)(\psi(b)-\psi(a))>0.
\end{align}In english, this means either $a<b$ and $\psi(a)<\psi(b)$, or $a>b$ and $\psi(a)>\psi(b)$.Then $N$ also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi(b)-\psi(a))(\psi^2(b)-\psi^2(a))>0,
\end{align}and also counts the number of pairs $(a,b)$ with $a\neq b$, satisfying \begin{align}
(\psi^2(b)-\psi^2(a))(b-a)>0.
\end{align}However, for each pair $(a,b)$ with $a\neq b$, at least one of the three equations $(1),(2),(3)$ are satisfied (as the product of all three is positive). By a Double Counting argument, running across all $(p-2)(p-3)$ pairs $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, we get $$N\geq \frac{(p-2)(p-3)}{3}.$$
Finally, we note that for $(a,b)\in \{2,\dots,p-1\}^2$ with $a\neq b$, that $$(\sigma(a)-\sigma(b))(\psi(a)-\psi(b))<0.$$
Therefore, the the number of pairs $(a,b) \in \{1,2,\cdots,p-1\}^2$ with $a<b$ but $\sigma(a) > \sigma(b)$ is exactly equal to $$\frac{N}{2}\geq \frac{(p-2)(p-3)}{6}\geq \left\lfloor \left(\frac{p-1}{4}\right)^2 \right \rfloor$$where the factor of half arises from WLOG $a<b$. The final inequality may be verified to be true for $p=3$ and $p\geq 5$.
such a nice solution