1987 AIME Problem 13

A given sequence r_{1}, r_{2}, \ldots, 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 current 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 on the right 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

\begin{tabular}{llll} 1 & 9 & 8 & 7 \\ 1 & 9 & 8 & 7 \\ 1 & 8 & 9 & 7 \\ 1 & 8 & 7 & 9 \\ \end{tabular}

underlined.

Suppose that n=40, and that the terms of the initial sequence r_{1}, r_{2}, \ldots, 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^{\text {th }} place (i. e., will have 29 terms on its left and 10 terms on its right). Find p+q.