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 "Mock AIME I 2012 Problems/Problem 5"

(Created page with "==Problem== Define a \emph{triple inequality} to be an inequality of the form <math>r_i > r_j > r_k</math>. Bradley has a list of 50 real numbers <math>(r_1, r_2, \cdots, r_{50})...")
 
Line 3: Line 3:
  
 
==Solution==
 
==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 <math>2k(48-k)</math> inequalities of the form <math>x > y > z</math> where <math>y</math> is one of the 2 uncertain numbers, <math>x</math> is one of the <math>k</math> numbers greater than the two uncertain ones, and <math>z</math> is one of the <math>48-k</math> 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 <math>k = 24</math> for a total of 1152 inequalities of this form. When only one of <math>x</math> or <math>z</math> is one of these two middle numbers, we get another <math>2 �\cdot 2 \binom{ 24}{2}= 1104</math> inequalities. And there are <math>\binom{48}{3}= 17296</math> inequalities where the order of <math>x</math>, <math>y</math>, and <math>z</math> is fixed. Adding all the possibilities gives 19552, so our answer is <math>\boxed{552}</math>.
+
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 <math>2k(48-k)</math> inequalities of the form <math>x > y > z</math> where <math>y</math> is one of the 2 uncertain numbers, <math>x</math> is one of the <math>k</math> numbers greater than the two uncertain ones, and <math>z</math> is one of the <math>48-k</math> 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 <math>k = 24</math> for a total of 1152 inequalities of this form. When only one of <math>x</math> or <math>z</math> is one of these two middle numbers, we get another <math>2 \cdot 2 \binom{ 24}{2}= 1104</math> inequalities. And there are <math>\binom{48}{3}= 17296</math> inequalities where the order of <math>x</math>, <math>y</math>, and <math>z</math> is fixed. Adding all the possibilities gives 19552, so our answer is <math>\boxed{552}</math>.

Revision as of 16:35, 7 April 2012

Problem

Define a \emph{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}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_5&oldid=46183"