Difference between revisions of "2017 USAMO Problems/Problem 2"
m (→Problem) |
Scrabbler94 (talk | contribs) m (→Problem: added full text of problem) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | ==Problem== | |
| + | 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 18: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:
![\[a_i \ge w_i > w_j,\]](http://latex.artofproblemsolving.com/d/9/e/d9e7a57a108c19f542380b6fa1beb50678c4c673.png)
![\[w_j > a_i \ge w_i,\]](http://latex.artofproblemsolving.com/f/5/4/f549c84bc48a26d35304ddc3d5ea8ff3bfdda743.png)
or
![\[w_i > w_j > a_i.\]](http://latex.artofproblemsolving.com/d/8/4/d846c7956ec8bfa8606414225de394a6712e90fb.png)
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.
