Difference between revisions of "1987 AIME Problems/Problem 13"
m (→Solution) |
(Solution 2) |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | A given [[sequence]] <math> | + | A given [[sequence]] <math>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>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> | + | Suppose that <math>n = 40</math>, and that the terms of the initial sequence <math>r_1, r_2, \dots, r_{40}</math> are distinct from one another and are in random order. Let <math>p/q</math>, in lowest terms, be the [[probability]] that the number that begins as <math>r_{20}</math> will end up, after one bubble pass, in the <math>30^{\mbox{th}}</math> place. Find <math>p + q</math>. |
− | == Solution == | + | == Solution 1 == |
− | If any of <math>r_1, \ldots, r_{19}</math> is larger than <math>r_{20}</math>, | + | If any of <math>r_1, \ldots, r_{19}</math> is larger than <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 31 distinct real numbers, the largest is in position 31 and the second-largest is in position 20 (the other 29 numbers are irrelevant)? | Thus, our problem can be restated: What is the probability that in a sequence of 31 distinct real numbers, the largest is in position 31 and the second-largest is in position 20 (the other 29 numbers are irrelevant)? | ||
− | This is much easier to solve: there are <math>31!</math> ways to order 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. This gives us a desired probability of <math>\frac{29!}{31!} = \frac{1}{31\cdot 30} = \frac{1}{930}</math>, so the answer is <math>931</math>. | + | This is much easier to solve: there are <math>31!</math> ways to order 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. This gives us a desired probability of <math>\frac{29!}{31!} = \frac{1}{31\cdot 30} = \frac{1}{930}</math>, so the answer is <math>\boxed{931}</math>. |
+ | |||
+ | ===Remark=== | ||
+ | Note that you can solve the restated problem differently: | ||
+ | |||
+ | We see that the numerator is <math>1</math> because there is only <math>1</math> way to make the <math>31^{\text{st}}</math> term the largest and the <math>20^{\text{th}}</math> the second-largest. To calculate the denominator, we note that there are <math>31\times30</math> ways to pick the largest term and the second-largest term. Therefore, our answer is <math>\boxed{931}</math>. | ||
+ | ~Yiyj1 | ||
+ | |||
+ | == Solution 2 (Summations) == | ||
+ | Assume we have a set of <math>40</math> numbers, all distinct, that will be randomly shuffled. We wish to find the number of ways that the following conditions are satisfied: | ||
+ | |||
+ | <math>1.</math> The greatest number out of the first <math>30</math> terms is located at the <math>20</math>th place, and | ||
+ | |||
+ | <math>2.</math> Term <math>31</math> is greater than term <math>20</math>. | ||
+ | |||
+ | <math>3.</math> The final <math>9</math> terms can be in any order. | ||
+ | |||
+ | Let the resulting term <math>20</math> be notated as <math>X</math>. We then set up a dummy variable <math>k</math> such that <math>k</math> describes the number of terms (out of <math>40</math>) that are less than <math>X</math>. For instance, if there were <math>29</math> terms less than <math>X</math>, the dummy variable <math>k</math> would be <math>29</math>. Now we can set up our summation. | ||
+ | |||
+ | <math>1.</math> To make sure the first condition is met, we perform the following: We know that there are <math>k</math> terms less than <math>X</math>, so thus there are <math>\frac{k!}{(k-29)!}</math> ways to place <math>29</math> of the <math>k</math> terms in a specific order. | ||
+ | |||
+ | <math>2.</math> For the second condition, there are <math>39-k</math> terms greater than <math>X</math>, so there are <math>39-k</math> ways to place the number greater than <math>X</math> in the <math>31</math>st placement. | ||
+ | |||
+ | <math>3.</math> Finally, since the final <math>9</math> terms can be in any order, there are <math>9!</math> ways to place these numbers. | ||
+ | |||
+ | (The three steps above all correspond to the three conditions given at the beginning of the solution.) | ||
+ | |||
+ | However, we need to set lower and upper bounds for <math>k</math> in order to calculate our summation. Looking at the range of <math>k</math>, we see that there must be at least <math>29</math> numbers less than <math>X</math> in order for condition <math>1</math> to be satisfied. There must be at least <math>1</math> number greater than <math>X</math> in order for condition <math>2</math> to be satisfied as well, leaving a maximum of <math>38</math> numbers less than <math>X</math>. Thus, <math>k</math> ranges from <math>29</math> to <math>38</math>. | ||
+ | |||
+ | Finally, we divide the entire value by <math>40!</math> as there are <math>40!</math> ways to arrange the <math>40</math> terms. This step could also be performed at the very end. At this point, we are ready to calculate the summation. | ||
+ | |||
+ | |||
+ | <math>\frac{1}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}(39-k)\cdot9!\right)</math> | ||
+ | |||
+ | <math>=\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}(39-k)\right)</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot39}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}\right)-\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!\cdot k}{(k-29)!}\right)</math> | ||
+ | |||
+ | Now we deal with each sum separately. Looking at the first sum, we see that the factorials inside the summation bear a close resemblance to <math>{k\choose29}</math>. Indeed, we are able to use this to our advantage: | ||
+ | |||
+ | <math>\frac{9!\cdot39}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot39\cdot29!}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!\cdot29!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot39\cdot29!}{40!}\sum_{k=29}^{38}{k\choose29}</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot39\cdot29!}{40!}{39\choose30}</math> | ||
+ | |||
+ | (The last equality is thanks to the [[Hockey-Stick Identity]].) | ||
+ | |||
+ | The second sum is similar to the first, but we must first replace <math>k</math> with <math>(k+1)-1</math>: | ||
+ | |||
+ | <math>\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!\cdot k}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!\cdot(k+1-1)}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!\cdot(k+1)}{(k-29)!}\right)-\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{(k+1)!}{(k-29)!}\right)-\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot30!}{40!}\sum_{k=29}^{38}{k+1\choose30}-\frac{9!\cdot29!}{40!}\sum_{k=29}^{38}{k\choose29}</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot30!}{40!}{40\choose31}-\frac{9!\cdot29!}{40!}{39\choose30}</math> | ||
+ | |||
+ | We are finally able to calculate the end result: | ||
+ | |||
+ | <math>\frac{9!\cdot39}{40!}\sum_{k=29}^{38}\left(\frac{k!}{(k-29)!}\right)-\frac{9!}{40!}\sum_{k=29}^{38}\left(\frac{k!\cdot k}{(k-29)!}\right)</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot39\cdot29!}{40!}{39\choose30}-\frac{9!\cdot30!}{40!}{40\choose31}+\frac{9!\cdot29!}{40!}{39\choose30}</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot40\cdot29!}{40!}{39\choose30}-\frac{9!\cdot30!}{40!}{40\choose31}</math> | ||
+ | |||
+ | <math>=\frac{9!\cdot29!\cdot39!}{39!\cdot9!\cdot30!}-\frac{9!\cdot30!\cdot40!}{40!\cdot9!\cdot31!}</math> | ||
+ | |||
+ | <math>=\frac{29!}{30!}-\frac{30!}{31!}</math> | ||
+ | |||
+ | <math>=\frac{1}{30}-\frac{1}{31}</math> | ||
+ | |||
+ | <math>=\frac{31}{930}-\frac{30}{930}</math> | ||
+ | |||
+ | <math>=\frac{1}{930}</math> | ||
+ | |||
+ | Thus our answer is <math>1+930=\boxed{931}</math>. | ||
+ | |||
+ | ~eevee9406 | ||
== See also == | == See also == | ||
Line 20: | Line 104: | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 10:55, 26 June 2024
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.
![$\underline{1 \quad 9} \quad 8 \quad 7$](http://latex.artofproblemsolving.com/9/a/7/9a758444e2fe7e0b5baf53b10fb46fc82578f76f.png)
![$1 \quad {}\underline{9 \quad 8} \quad 7$](http://latex.artofproblemsolving.com/5/e/1/5e128f2e30cf1ccbec3eeb417a253878769a6146.png)
![$1 \quad 8 \quad \underline{9 \quad 7}$](http://latex.artofproblemsolving.com/d/4/4/d44d1ef233c13008dad6dbc8b15e2a55fa832ffc.png)
![$1 \quad 8 \quad 7 \quad 9$](http://latex.artofproblemsolving.com/d/c/d/dcd6f6c706ef68815562956944a168b3afe7dcf2.png)
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 1
If any of is larger than
, one of these numbers will be compared with
on the 19th step of the first bubble pass and
will be moved back to the 19th position. Thus,
must be the largest of the first 20 terms. In addition,
must be larger than
but smaller than
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 31 distinct real numbers, the largest is in position 31 and the second-largest is in position 20 (the other 29 numbers are irrelevant)?
This is much easier to solve: there are ways to order the first thirty-one numbers and
ways to arrange them so that the largest number is in the 31st position and the second-largest is in the 20th. This gives us a desired probability of
, so the answer is
.
Remark
Note that you can solve the restated problem differently:
We see that the numerator is because there is only
way to make the
term the largest and the
the second-largest. To calculate the denominator, we note that there are
ways to pick the largest term and the second-largest term. Therefore, our answer is
.
~Yiyj1
Solution 2 (Summations)
Assume we have a set of numbers, all distinct, that will be randomly shuffled. We wish to find the number of ways that the following conditions are satisfied:
The greatest number out of the first
terms is located at the
th place, and
Term
is greater than term
.
The final
terms can be in any order.
Let the resulting term be notated as
. We then set up a dummy variable
such that
describes the number of terms (out of
) that are less than
. For instance, if there were
terms less than
, the dummy variable
would be
. Now we can set up our summation.
To make sure the first condition is met, we perform the following: We know that there are
terms less than
, so thus there are
ways to place
of the
terms in a specific order.
For the second condition, there are
terms greater than
, so there are
ways to place the number greater than
in the
st placement.
Finally, since the final
terms can be in any order, there are
ways to place these numbers.
(The three steps above all correspond to the three conditions given at the beginning of the solution.)
However, we need to set lower and upper bounds for in order to calculate our summation. Looking at the range of
, we see that there must be at least
numbers less than
in order for condition
to be satisfied. There must be at least
number greater than
in order for condition
to be satisfied as well, leaving a maximum of
numbers less than
. Thus,
ranges from
to
.
Finally, we divide the entire value by as there are
ways to arrange the
terms. This step could also be performed at the very end. At this point, we are ready to calculate the summation.
Now we deal with each sum separately. Looking at the first sum, we see that the factorials inside the summation bear a close resemblance to . Indeed, we are able to use this to our advantage:
(The last equality is thanks to the Hockey-Stick Identity.)
The second sum is similar to the first, but we must first replace with
:
We are finally able to calculate the end result:
Thus our answer is .
~eevee9406
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.