Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1987 AIME Problems/Problem 13"

m
(solved)
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.  
+
A given [[sequence]] <math>\displaystyle r_1, r_2, \dots, r_n</math> of [[distinct]] [[real number]]s 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.
 
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.
Line 7: Line 7:
 
<center><math>1 \quad 8 \quad \underline{9 \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>
 
<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>.
+
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}}
+
If any of <math>r_1, \ldots, r_{19}</math> is larger than <math>r_{20}</math>, <math>r_{20}</math> one of these numbers will be compared with <math>r_{20}</math> on the 19th step of the first bubble pass and <math>r_{20}</math> will be moved back to the 19th position.  Thus, <math>r_{20}</math> must be the largest of the first 20 terms.  In addition, <math>r_{20}</math> must be larger than <math>r_{21}, r_{22}, \ldots, r_{30}</math> but smaller than <math>r_{31}</math> in order that it move right to the 30th position but then not continue moving right to the 31st.
 +
 
 +
Thus, our problem can be restated: What is the probability that in a sequence of 40 distinct real numbers, among the first 31, the largest is in position 31 and the second-largest is in position 20?
 +
 
 +
This is much easier to solve: there are <math>40 \choose 31</math> ways to pick the first thirty-one numbers and <math>29!</math> ways to arrange them so that the largest number is in the 31st position and the second-largest is in the 20th.  There are also <math>9!</math> ways to arrange the remaining nine members of the sequence.  This is out of a total of <math>40!</math> possible [[permutation]]s of the sequence.  This gives us a desired probability of <math>\frac{{40 \choose 31} \cdot 29! \cdot 9!}{40!} = \frac{1}{30\cdot 31} = \frac{1}{930}</math>, so the answer is <math>931</math>.
 +
 
 
== See also ==
 
== See also ==
−
* [[1987 AIME Problems]]
+
* [[Factorial]]
 +
{{AIME box|year=1987|num-b=12|num-a=14}}
  
−
{{AIME box|year=1987|num-b=12|num-a=14}}
+
[[Category:Intermediate Combinatorics Problems]]

Revision as of 09:44, 11 February 2007

Problem

A given sequence $\displaystyle r_1, r_2, \dots, 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, $\displaystyle 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.

$\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$

Suppose that $\displaystyle n = 40$, and that the terms of the initial sequence $\displaystyle r_1, r_2, \dots, r_{40}$ are distinct from one another and are in random order. Let $\displaystyle p/q$, in lowest terms, be the probability that the number that begins as $\displaystyle r_{20}$ will end up, after one bubble pass, in the $\displaystyle 30^{\mbox{th}}$ place. Find $\displaystyle p + q$.

Solution

If any of $r_1, \ldots, r_{19}$ is larger than $r_{20}$, $r_{20}$ one of these numbers will be compared with $r_{20}$ on the 19th step of the first bubble pass and $r_{20}$ will be moved back to the 19th position. Thus, $r_{20}$ must be the largest of the first 20 terms. In addition, $r_{20}$ must be larger than $r_{21}, r_{22}, \ldots, r_{30}$ but smaller than $r_{31}$ in order that it move right to the 30th position but then not continue moving right to the 31st.

Thus, our problem can be restated: What is the probability that in a sequence of 40 distinct real numbers, among the first 31, the largest is in position 31 and the second-largest is in position 20?

This is much easier to solve: there are $40 \choose 31$ ways to pick the first thirty-one numbers and $29!$ ways to arrange them so that the largest number is in the 31st position and the second-largest is in the 20th. There are also $9!$ ways to arrange the remaining nine members of the sequence. This is out of a total of $40!$ possible permutations of the sequence. This gives us a desired probability of $\frac{{40 \choose 31} \cdot 29! \cdot 9!}{40!} = \frac{1}{30\cdot 31} = \frac{1}{930}$, so the answer is $931$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1987_AIME_Problems/Problem_13&oldid=13123"