1987 AIME Problems/Problem 13
Problem
A given sequence of distinct real numbers can be put in ascending order by means of one or more "bubble passes". A bubble pass through a given sequence consists of comparing the second term with the first term, and exchanging them if and only if the second term is smaller, then comparing the third term with the second term and exchanging them if and only if the third term is smaller, and so on in order, through comparing the last term,
, with its current predecessor and exchanging them if and only if the last term is smaller.
The example below shows how the sequence 1, 9, 8, 7 is transformed into the sequence 1, 8, 7, 9 by one bubble pass. The numbers compared at each step are underlined.
![$\underline{1 \quad 9} \quad 8 \quad 7$](http://latex.artofproblemsolving.com/9/a/7/9a758444e2fe7e0b5baf53b10fb46fc82578f76f.png)
![$1 \quad {}\underline{9 \quad 8} \quad 7$](http://latex.artofproblemsolving.com/5/e/1/5e128f2e30cf1ccbec3eeb417a253878769a6146.png)
![$1 \quad 8 \quad \underline{9 \quad 7}$](http://latex.artofproblemsolving.com/d/4/4/d44d1ef233c13008dad6dbc8b15e2a55fa832ffc.png)
![$1 \quad 8 \quad 7 \quad 9$](http://latex.artofproblemsolving.com/d/c/d/dcd6f6c706ef68815562956944a168b3afe7dcf2.png)
Suppose that , and that the terms of the initial sequence
are distinct from one another and are in random order. Let
, in lowest terms, be the probability that the number that begins as
will end up, after one bubble pass, in the
place. Find
.
Solution
If any of is larger than
, one of these numbers will be compared with
on the 19th step of the first bubble pass and
will be moved back to the 19th position. Thus,
must be the largest of the first 20 terms. In addition,
must be larger than
but smaller than
in order that it move right to the 30th position but then not continue moving right to the 31st.
Thus, our problem can be restated: What is the probability that in a sequence of 31 distinct real numbers, the largest is in position 31 and the second-largest is in position 20 (the other 29 numbers are irrelevant)?
This is much easier to solve: there are ways to order the first thirty-one numbers and
ways to arrange them so that the largest number is in the 31st position and the second-largest is in the 20th. This gives us a desired probability of
, so the answer is
.
See also
1987 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.