Difference between revisions of "2001 AIME I Problems/Problem 6"
I_like_pie (talk | contribs) |
(5 solutions, hope thats enough :)) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | A fair die is rolled four times. The [[probability]] that each of the final three rolls is at least as large as the roll preceding it may be expressed in the form <math>\frac{m}{n}</math> where <math>m</math> and <math>n</math> are [[relatively prime]] [[positive]] [[integer]]s. Find <math>m + n</math>. | ||
+ | __TOC__ | ||
== Solution == | == Solution == | ||
+ | === Solution 1 === | ||
+ | If we take any [[permutation]] of four numbers, there is only one way to order them (there is a [[bijection|one-to-one correspondence]]) in an non-decreasing order. We can visualize this as taking the four dice and splitting them into 6 slots (each slot representing one possible roll), or dividing them amongst 5 separators. Thus, there are <math>{9\choose4} = 126</math> outcomes of four dice. The solution is thus <math>\frac{126}{6^4} = \frac{7}{72}</math>, and <math>7 + 72 = 079</math>. | ||
+ | |||
+ | === Solution 2 === | ||
+ | Call the dice rolls <math>a, b, c, d</math>. The difference between the <math>a</math> and <math>d</math> distinguishes the number of possibile rolls there are. | ||
+ | |||
+ | *If <math>a - d = 0</math>, then the values of <math>b,\ c</math> are set, and so there are <math>6</math> values for <math>a,\ d</math>. | ||
+ | *If <math>a - d = 1</math>, then there are <math>{3\choose2} = 3</math> ways to arrange for values of <math>b,\ c</math>, but only <math>5</math> values for <math>a,\ d</math>. | ||
+ | *If <math>a - d = 2</math>, then there are <math>{4\choose2} = 6</math> ways to arrange <math>b, c</math>, and there are only <math>6 - 2 = 4</math> values for <math>\displaystyle a, d</math>. | ||
+ | |||
+ | Continuing, we see that the sum is equal to <math>\displaystyle\sum_{i = 0}^{5}{i+2\choose2}(6 - i) = 6 + 15 + 24 + 30 + 30 + 21 = 126</math>. The requested probability is <math>\frac{126}{6^4} = \frac{7}{72}</math>. | ||
+ | |||
+ | === Solution 3 === | ||
+ | The dice rolls can be in the form | ||
+ | |||
+ | <div style="text-align:center;"> | ||
+ | ABCD<br /> | ||
+ | AABC<br /> | ||
+ | AABB<br /> | ||
+ | AAAB<br /> | ||
+ | AAAA | ||
+ | </div> | ||
+ | |||
+ | where A, B, C, D are some possible value of the dice rolls. (These forms are not keeping track of whether or not the dice are in ascending order, just the possible outcomes.) | ||
+ | |||
+ | #Now, for the first case, there are <math>{6\choose4} = 15</math> ways for this. We do not have to consider the order because the combination counts only one of the permutations; we can say that it counts the correct (ascending order) permutation. | ||
+ | #Second case: <math>{6\choose3} = 20</math> ways to pick 3 numbers, <math>{3\choose1}</math> ways to pick 1 of those 3 to duplicate. A total of 60 for this case. | ||
+ | #Third case: <math>{6\choose2}=15</math> ways to pick 2 numbers. We will duplicate both, so nothing else in this case matters. | ||
+ | #Fourth case: <math>{6\choose2} = 15</math> ways to pick 2 numbers. We pick one to duplicate with <math>{2\choose1} = 2</math>, so there are a total of 30 in this case. | ||
+ | #Fifth case: <math>{6\choose1} = 6</math>; all get duplicated so nothing else matters. | ||
+ | |||
+ | There are a total of <math>6^4</math> possible dice rolls. | ||
+ | |||
+ | Thus, | ||
+ | |||
+ | <div style="text-align:center;"><math>\frac{m}{n} = \frac{15 + 60 + 15 + 30 + 6}{6^4} = \frac{126}{6^4} = \frac{7}{72}</math></div> | ||
+ | |||
+ | === Solution 4 === | ||
+ | Consider the number of possible dice roll combinations which work after <math>1</math> roll, after <math>2</math> rolls, and so on. There is 6 possible rolls for the first dice. If the number rolled is a 1, then there are 6 further values that are possible for the second dice; if the number rolled is a 2, then there are 5 further values that are possible for the second dice, and so on. | ||
+ | |||
+ | Suppose we generalize this as a function, say <math>f(l,r)</math> return the number of possible combinations after <math>l</math> rolls and <math>r</math> being the beginning value of the first roll. It becomes clear that from above, <math>f(1,r) = 1</math>; every value of <math>l</math> after that is equal to the sum of the number of combinations of <math>l - 1</math> rolls that have a starting value of at least <math>r</math>. If we slowly count through and add up all the possible combinations we get <math>\frac{7}{72}</math> possibilities. | ||
+ | |||
+ | === Solution 5 === | ||
+ | In a manner similar to the above solution, instead consider breaking it down into two sets of two dice rolls. The first [[subset]] must have a maximum value which is <math>\le</math> the minimum value of the second subset. | ||
+ | |||
+ | *If the first subset ends in a 1, there is <math>1</math> such subset and there are <math>6 + 5 + 4 + 3 + 2 + 1 = \frac{6}{2}(6 + 1) = 21</math> ways of making the second subset. | ||
+ | *If the first subset ends in a 2, there is <math>2</math> such subsets and there are <math>5 + \ldots + 1 = \frac{5}{2}(5 + 1) = 15</math> ways of making the second subset. | ||
+ | |||
+ | Thus, the number of combinations is <math>\displaystyle\sum_{i=1}^6 i \cdot \left(\frac{(7 - i)(8 - i)}{2}\right) = 21 + 30 + 30 + 24 + 15 + 6 = 126</math>, and the probability again is <math>\frac7{72}</math>. | ||
== See also == | == See also == | ||
− | + | {{AIME box|year=2001|n=I|num-b=5|num-a=7}} | |
− | |||
− | |||
− | + | [[Category:Intermediate Combinatorics Problems]] |
Revision as of 18:05, 12 March 2007
Problem
A fair die is rolled four times. The probability that each of the final three rolls is at least as large as the roll preceding it may be expressed in the form where and are relatively prime positive integers. Find .
Contents
Solution
Solution 1
If we take any permutation of four numbers, there is only one way to order them (there is a one-to-one correspondence) in an non-decreasing order. We can visualize this as taking the four dice and splitting them into 6 slots (each slot representing one possible roll), or dividing them amongst 5 separators. Thus, there are outcomes of four dice. The solution is thus , and .
Solution 2
Call the dice rolls . The difference between the and distinguishes the number of possibile rolls there are.
- If , then the values of are set, and so there are values for .
- If , then there are ways to arrange for values of , but only values for .
- If , then there are ways to arrange , and there are only values for .
Continuing, we see that the sum is equal to . The requested probability is .
Solution 3
The dice rolls can be in the form
ABCD
AABC
AABB
AAAB
AAAA
where A, B, C, D are some possible value of the dice rolls. (These forms are not keeping track of whether or not the dice are in ascending order, just the possible outcomes.)
- Now, for the first case, there are ways for this. We do not have to consider the order because the combination counts only one of the permutations; we can say that it counts the correct (ascending order) permutation.
- Second case: ways to pick 3 numbers, ways to pick 1 of those 3 to duplicate. A total of 60 for this case.
- Third case: ways to pick 2 numbers. We will duplicate both, so nothing else in this case matters.
- Fourth case: ways to pick 2 numbers. We pick one to duplicate with , so there are a total of 30 in this case.
- Fifth case: ; all get duplicated so nothing else matters.
There are a total of possible dice rolls.
Thus,
Solution 4
Consider the number of possible dice roll combinations which work after roll, after rolls, and so on. There is 6 possible rolls for the first dice. If the number rolled is a 1, then there are 6 further values that are possible for the second dice; if the number rolled is a 2, then there are 5 further values that are possible for the second dice, and so on.
Suppose we generalize this as a function, say return the number of possible combinations after rolls and being the beginning value of the first roll. It becomes clear that from above, ; every value of after that is equal to the sum of the number of combinations of rolls that have a starting value of at least . If we slowly count through and add up all the possible combinations we get possibilities.
Solution 5
In a manner similar to the above solution, instead consider breaking it down into two sets of two dice rolls. The first subset must have a maximum value which is the minimum value of the second subset.
- If the first subset ends in a 1, there is such subset and there are ways of making the second subset.
- If the first subset ends in a 2, there is such subsets and there are ways of making the second subset.
Thus, the number of combinations is , and the probability again is .
See also
2001 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 5 |
Followed by Problem 7 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |