Problem #153

153.

A given sequence $r_1, r_2, \dots, r_n$ 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, $r_n$, 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$
$1 \quad {}\underline{9 \quad 8} \quad 7$
$1 \quad 8 \quad \underline{9 \quad 7}$
$1 \quad 8 \quad 7 \quad 9$

Suppose that $n = 40$, and that the terms of the initial sequence $r_1, r_2, \dots, r_{40}$ are distinct from one another and are in random order. Let $p/q$, in lowest terms, be the probability that the number that begins as $r_{20}$ will end up, after one bubble pass, in the $30^{\mbox{th}}$ place. Find $p + q$.

This problem is copyrighted by the American Mathematics Competitions.

Note: you aren't logged in. If you log in, we'll keep a record of which problems you've solved.

Instructions for entering answers:

  • Reduce fractions to lowest terms and enter in the form 7/9.
  • Numbers involving pi should be written as 7pi or 7pi/3 as appropriate.
  • Square roots should be written as sqrt(3), 5sqrt(5), sqrt(3)/2, or 7sqrt(2)/3 as appropriate.
  • Exponents should be entered in the form 10^10.
  • If the problem is multiple choice, enter the appropriate (capital) letter.
  • Enter points with parentheses, like so: (4,5)
  • Complex numbers should be entered in rectangular form unless otherwise specified, like so: 3+4i. If there is no real component, enter only the imaginary component (i.e. 2i, NOT 0+2i).

For questions or comments, please email markan@eudelic.com.

Registration open for AMC10/12 prep class

Registration is now open. See details here.