USAMO 2017 Problem 2
Let \(m_1, m_2, \ldots, m_n\) be a collection of \(n\) positive integers, not necessarily distinct. For any sequence of integers \(A = (a_1, \ldots, a_n)\) and any permutation \(w = w_1, \ldots, w_n\) of \(m_1, \ldots, m_n\), define an \(A\)-inversion of \(w\) to be a pair of entries \(w_i, w_j\) with \(i < j\) for which one of the following conditions holds:
\(a_i \ge w_i > w_j\),
\(w_j > a_i \ge w_i\),
\(w_i > w_j > a_i\).
Show that, for any two sequences of integers \(A = (a_1, \ldots, a_n)\) and \(B = (b_1, \ldots, b_n)\), and for any positive integer \(k\), the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(A\)-inversions is equal to the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(B\)-inversions.
==========================================================
Proof:
It suffices to show that swapping any \(a_i\) with \(a_{i+1}\) does not alter the distribution of number of \(A\)-inversions, as then any sequence \(A\) could be transformed to any other sequence \(B\) with a combination of such swapping and update of the last element \(a_n\).
\(a_i \ge w_i > w_j\),
\(w_j > a_i \ge w_i\),
\(w_i > w_j > a_i\).
Show that, for any two sequences of integers \(A = (a_1, \ldots, a_n)\) and \(B = (b_1, \ldots, b_n)\), and for any positive integer \(k\), the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(A\)-inversions is equal to the number of permutations of \(m_1, \ldots, m_n\) having exactly \(k\) \(B\)-inversions.
==========================================================
Proof:
It suffices to show that swapping any \(a_i\) with \(a_{i+1}\) does not alter the distribution of number of \(A\)-inversions, as then any sequence \(A\) could be transformed to any other sequence \(B\) with a combination of such swapping and update of the last element \(a_n\).
post by Shen-Fu Tsai