Difference between revisions of "2017 USAMO Problems/Problem 2"
Mathcounts46 (talk | contribs) (Created page with "==Problem== Let <math>m_1,\dotsc,m_n</math> be a collection of <math>n</math> positive integers, not necessarily distinct. For any sequence of integers <math>A = (a_1,\dotsc,a...") |
Scrabbler94 (talk | contribs) m (→Problem: added full text of problem) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Let <math>m_1,\ | + | Let <math>m_1, m_2, \ldots, m_n</math> be a collection of <math>n</math> positive integers, not necessarily distinct. For any sequence of integers <math>A = (a_1, \ldots, a_n)</math> and any permutation <math>w = w_1, \ldots, w_n</math> of <math>m_1, \ldots, m_n</math>, define an <math>A</math>-inversion of <math>w</math> to be a pair of entries <math>w_i, w_j</math> with <math>i < j</math> for which one of the following conditions holds: |
+ | |||
+ | <cmath>a_i \ge w_i > w_j,</cmath> | ||
+ | <cmath>w_j > a_i \ge w_i,</cmath> | ||
+ | or | ||
+ | <cmath>w_i > w_j > a_i.</cmath> | ||
+ | Show that, for any two sequences of integers <math>A = (a_1, \ldots, a_n)</math> and <math>B = (b_1, \ldots, b_n)</math>, and for any positive integer <math>k</math>, the number of permutations of <math>m_1, \ldots, m_n</math> having exactly <math>k</math> <math>A</math>-inversions is equal to the number of permutations of <math>m_1, \ldots, m_n</math> having exactly <math>k</math> <math>B</math>-inversions. |
Latest revision as of 19:48, 21 November 2018
Problem
Let be a collection of
positive integers, not necessarily distinct. For any sequence of integers
and any permutation
of
, define an
-inversion of
to be a pair of entries
with
for which one of the following conditions holds:
or
Show that, for any two sequences of integers
and
, and for any positive integer
, the number of permutations of
having exactly
-inversions is equal to the number of permutations of
having exactly
-inversions.