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$ .