Mock AIME I 2012 Problems/Problem 5
Problem
Define a \emph{triple inequality} to be an inequality of the form . Bradley has a list of 50 real numbers
, 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
, Batra knows that the 7th number is greater than the 2nd number which is greater than the 49th number, but nothing else. Let
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
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 inequalities of the form
where
is one of the 2 uncertain numbers,
is one of the
numbers greater than the two uncertain ones, and
is one of the
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
for a total of 1152 inequalities of this form. When only one of
or
is one of these two middle numbers, we get another
inequalities. And there are
inequalities where the order of
,
, and
is fixed. Adding all the possibilities gives 19552, so our answer is
.