Câu hỏi 13
Một chuỗi $r_1,$ $r_2,$ $\ldots,$ $r_n$ gồm các số thực riêng biệt có thể được sắp xếp theo thứ tự tăng dần bằng một hoặc nhiều “bubble pass”. Một bong bóng đi qua một chuỗi nhất định bao gồm việc so sánh số hạng thứ hai với số hạng đầu tiên và hoán đổi chúng khi và chỉ khi số hạng thứ hai nhỏ hơn, sau đó so sánh số hạng thứ ba với số hạng thứ hai và hoán đổi chúng khi và chỉ khi số hạng thứ ba nhỏ hơn, v.v. theo thứ tự, thông qua việc so sánh số hạng cuối cùng, $r_n,$ với số hạng trước đó hiện tại và hoán đổi chúng khi và chỉ nếu số hạng cuối cùng nhỏ hơn.
Ví dụ bên dưới cho thấy cách chuyển đổi chuỗi $1,$ $9,$ $8,$ $7$ thành chuỗi $1,$ $8,$ $7,$ $9$ bằng một lần chuyển bong bóng. Các con số so sánh ở mỗi bước được gạch chân.
$$
\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}
$$
Giả sử rằng $n=40,$ và các số hạng của dãy ban đầu $r_1,$ $r_2,$ $\ldots,$ $r_{40}$ khác biệt với nhau và theo thứ tự ngẫu nhiên. Giả sử $\frac{p}{q},$ theo số hạng thấp nhất, là xác suất mà số bắt đầu là $r_{20}$ sẽ kết thúc ở vị trí thứ $30$ sau khi một bong bóng trôi qua. Tìm $p+q.$
Ví dụ bên dưới cho thấy cách chuyển đổi chuỗi $1,$ $9,$ $8,$ $7$ thành chuỗi $1,$ $8,$ $7,$ $9$ bằng một lần chuyển bong bóng. Các con số so sánh ở mỗi bước được gạch chân.
$$
\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}
$$
Giả sử rằng $n=40,$ và các số hạng của dãy ban đầu $r_1,$ $r_2,$ $\ldots,$ $r_{40}$ khác biệt với nhau và theo thứ tự ngẫu nhiên. Giả sử $\frac{p}{q},$ theo số hạng thấp nhất, là xác suất mà số bắt đầu là $r_{20}$ sẽ kết thúc ở vị trí thứ $30$ sau khi một bong bóng trôi qua. Tìm $p+q.$