Given a permutation of $1,2,3,\dots,n$, with consecutive elements $a,b,c$ (in that order), we may perform either of the moves: If $a$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $b,c,a$ (in that order) If $c$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $c,a,b$ (in that order) What is the least number of sets in a partition of all $n!$ permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves? Proposed by Milan Haiman
Problem
Source: 2019 ELMO Shortlist C5
Tags: combinatorics
a1267ab
28.06.2019 00:41
The Forgotten Monoid
Mikeglicker
14.08.2020 00:23
Bump This problem has no solution yet
M.Shahverdi
06.10.2020 14:28
Interesting problem! I guess the answer is $n^2 - 3n + 4$ and I proved the lower bound but couldn't prove the upper bound : In a permutation $\sigma$ we call a pair $(i,j)$ an inversion if $i < j$ and $\sigma (i) > \sigma(j)$. note1. These moves don't change the total number of inversions in the permutation. note2. We can't change the ordering between $1$ and $n$. So in each class of permutations such that any two permutations are obtainable from each other the ordering between $1$ and $n$ and also the total number of inversions are invariant. For a permutation $\sigma$ such that $1$ is before $n$ the number of inversions is a number between $0$ and $\frac{(n-1)(n-2)}{2}$ because other $n-2$ numbers can have at most $\frac{(n-2)(n-3)}{2}$ inversions and each of them can build $1$ or $0$ inversion with $1$ and $n$ and it's easy to see all of this cases are achievable. Similarly if $1$ is after $n$ the number of inversions is between $n-1$ and $\frac{(n)(n-1)}{2}$. So in both cases there exist $\frac{(n-1)(n-2)}{2} + 1$ choices for the number of inversions so the number of such classes is at least $n^2 - 3n +4$