Difference between revisions of "1987 AIME Problems/Problem 13"
m (→See also) |
m |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| + | A given sequence <math>\displaystyle r_1, r_2, \dots, r_n</math> 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, <math>\displaystyle r_n</math>, 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. | ||
| + | <center><math>\underline{1 \quad 9} \quad 8 \quad 7</math></center> | ||
| + | <center><math>1 \quad {}\underline{9 \quad 8} \quad 7</math></center> | ||
| + | <center><math>1 \quad 8 \quad \underline{9 \quad 7}</math></center> | ||
| + | <center><math>1 \quad 8 \quad 7 \quad 9</math></center> | ||
| + | Suppose that <math>\displaystyle n = 40</math>, and that the terms of the initial sequence <math>\displaystyle r_1, r_2, \dots, r_{40}</math> are distinct from one another and are in random order. Let <math>\displaystyle p/q</math>, in lowest terms, be the probability that the number that begins as <math>\displaystyle r_{20}</math> will end up, after one bubble pass, in the <math>\displaystyle 30^{\mbox{th}}</math> place. Find <math>\displaystyle p + q</math>. | ||
== Solution == | == Solution == | ||
| − | + | {{solution}} | |
== See also == | == See also == | ||
* [[1987 AIME Problems]] | * [[1987 AIME Problems]] | ||
{{AIME box|year=1987|num-b=12|num-a=14}} | {{AIME box|year=1987|num-b=12|num-a=14}} | ||
Revision as of 01:02, 11 February 2007
Problem
A given sequence 
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, 
, 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.
Suppose that 
, and that the terms of the initial sequence 
are distinct from one another and are in random order. Let 
, in lowest terms, be the probability that the number that begins as 
will end up, after one bubble pass, in the 
place. Find 
.
Solution
This problem needs a solution. If you have a solution for it, please help us out by adding it.
See also
| 1987 AIME (Problems • Answer Key • Resources) | ||
| Preceded by Problem 12 |
Followed by Problem 14 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
