2017 USAMO Problems/Problem 2

Problem

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

Page

Toolbox

Search

2017 USAMO Problems/Problem 2

Problem