Problemas de AIME 1987 Problema 13
Una secuencia dada \( r_1, r_2, \dots, r_n \) de números reales distintos se puede ordenar de menor a mayor mediante una o más “pasadas de burbuja”. Una pasada de burbuja a través de una secuencia dada consiste en comparar el segundo término con el primero, e intercambiarlos si y solo si el segundo término es menor; luego comparar el tercer término con el segundo e intercambiarlos si y solo si el tercero es menor, y así sucesivamente en orden, hasta comparar el último término, \( r_n \), con su predecesor actual e intercambiarlos si y solo si el último término es menor. El ejemplo siguiente muestra cómo la secuencia 1, 9, 8, 7 se transforma en la secuencia 1, 8, 7, 9 mediante una pasada de burbuja. Los números comparados en cada paso están subrayados. \[ \begin{array}{c} \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 \end{array} \] Supón que \( n = 40 \), y que los términos de la secuencia inicial \( r_1, r_2, \dots, r_{40} \) son distintos entre sí y están en orden aleatorio. Sea \( p/q \), en su forma reducida, la probabilidad de que el número que comienza como \( r_{20} \) termine, después de una pasada de burbuja, en el lugar \( 30^{\text{o}} \). Encuentra \( p + q \).
0
0
Inicia sesión para agregar soluciones y pistas