Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2017 USAMO Problems/Problem 2"

(Reinstate the problem text)
m (→‎Problem: added full text of problem)
 
Line 1: Line 1:
 
==Problem==
 
==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:
  
−
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_n)</math> and any permutation <math>w_1,\dotsc,w_n</math> of <math>m_1,\dotsc,m_n</math>, define an <math>A-inversion</math> 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 condition 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 $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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAMO_Problems/Problem_2&oldid=98888"