Mock AIME I 2012 Problems/Problem 5

Problem

Define a triple inequality to be an inequality of the form $r_i > r_j > r_k$ . Bradley has a list of 50 real numbers $(r_1, r_2, \cdots, r_{50})$ , but he will only give Batra triple inequalities consisting of 3 numbers in the list. For example, if Bradley gives Batra only the triple inequality $r_7 > r_2 > r_{49}$ , Batra knows that the 7th number is greater than the 2nd number which is greater than the 49th number, but nothing else. Let $N$ be the maximum number of (distinct) triple inequalities that Bradley could give Batra such that Batra cannot determine the order of the full list of 50 numbers. Find the remainder when $N$ is divided by 1000.

Solution

We can define the most inequalities if there is only uncertainty about the ordering of two numbers (which would then be adjacent to each other when the list is sorted by value). So if the list is sorted by value (say, from least to greatest) and there are numbers following the two uncertain ones, then we can come up with $2k(48-k)$ inequalities of the form $x > y > z$ where $y$ is one of the 2 uncertain numbers, $x$ is one of the $k$ numbers greater than the two uncertain ones, and $z$ is one of the $48-k$ numbers left over that must be less than the two uncertain ones. This is maximized when the two numbers are in the middle of the list, making $k = 24$ for a total of 1152 inequalities of this form. When only one of $x$ or $z$ is one of these two middle numbers, we get another $2 \cdot 2 \binom{ 24}{2}= 1104$ inequalities. And there are $\binom{48}{3}= 17296$ inequalities where the order of $x$ , $y$ , and $z$ is fixed. Adding all the possibilities gives 19552, so our answer is $\boxed{552}$ .

Page

Toolbox

Search

Mock AIME I 2012 Problems/Problem 5

Problem

Solution