Question

Una sucesión dada $r_1,$ $r_2,$ $\ldots,$ $r_n$ de números reales distintos puede ordenarse de menor a mayor mediante una o más «pasadas de burbuja». Una pasada de burbuja por una sucesión consiste en comparar el segundo término con el primero e intercambiarlos si y solo si el segundo es menor; después, comparar el tercero con el segundo e intercambiarlos si y solo si el tercero es menor; y continuar así, en orden, hasta comparar el último término, $r_n,$ con su predecesor actual e intercambiarlos si y solo si el último es menor.

El siguiente ejemplo muestra cómo una pasada de burbuja transforma la sucesión $1,$ $9,$ $8,$ $7$ en la sucesión $1,$ $8,$ $7,$ $9$ . Los números comparados en cada paso están subrayados.

$\begin{aligned} \underline{1}\quad\underline{9}\quad8\quad7\\ 1\quad\underline{9}\quad\underline{8}\quad7\\ 1\quad8\quad\underline{9}\quad\underline{7}\\ 1\quad8\quad7\quad9 \end{aligned}$

Supón que $n=40,$ y que los términos de la sucesión inicial $r_1,$ $r_2,$ $\ldots,$ $r_{40}$ son distintos entre sí y están en orden aleatorio. Sea $\frac{p}{q},$ como fracción irreducible, la probabilidad de que el número que inicialmente es $r_{20}$ termine, después de una pasada de burbuja, en el lugar $30$ . Halla $p+q.$

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 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.

$\begin{aligned} \underline{1}\quad\underline{9}\quad8\quad7\\ 1\quad\underline{9}\quad\underline{8}\quad7\\ 1\quad8\quad\underline{9}\quad\underline{7}\\ 1\quad8\quad7\quad9 \end{aligned}$

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 $\frac{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$ th place. Find $p+q.$

Respuesta

Respuesta: 931

Conceptos:probabilidad básica permutaciones simulación de procesos

Nivel de dificultad: 2450

Pista pequeña:

Después de la comparación que llega a la posición $j,$ esa posición contiene el máximo de los primeros $j$ términos originales

After the comparison reaching position $j,$ that position holds the maximum of the first $j$ original terms

Pista grande:

Caracteriza los rangos relativos de $r_{20}$ y $r_{31}$ entre los primeros $31$ términos

Characterize the relative ranks of $r_{20}$ and $r_{31}$ among the first $31$ terms

Solución:

Para que $r_{20}$ se desplace hacia la derecha hasta la posición $30,$ debe superar a todos los demás términos entre $r_1,\ldots,r_{30}.$ Se detiene exactamente en la posición $30$ cuando $r_{31}>r_{20}.$ Por tanto, entre los primeros $31$ términos, $r_{31}$ debe ser el mayor y $r_{20}$ el segundo mayor. Estas dos asignaciones ordenadas de posiciones tienen probabilidad $\frac1{31}\cdot\frac1{30}=\frac1{930}.$ Así, $p+q=1+930=931.$

For $r_{20}$ to move right to position $30,$ it must exceed every other term among $r_1,\ldots,r_{30}.$ It stops at position $30$ exactly when $r_{31}>r_{20}.$ Thus among the first $31$ terms, $r_{31}$ must be greatest and $r_{20}$ second greatest. These two ordered rank assignments have probability $\frac1{31}\cdot\frac1{30}=\frac1{930}.$ Therefore $p+q=1+930=931.$

1987 AIME Problema 13

Respuesta: 931

Nivel de dificultad: 2450

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años