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