Difference between revisions of "2001 AIME I Problems/Problem 6"
Skyscraper (talk | contribs) (→Solution 8: Observation of each case) |
Skyscraper (talk | contribs) (→Solution 8: Observation of each case(for when you have 30 seconds left) |
||
Line 75: | Line 75: | ||
and | and | ||
<cmath> P = \frac{N}{6^4}</cmath> | <cmath> P = \frac{N}{6^4}</cmath> | ||
− | ==Solution 8: Observation of each case | + | ==Solution 8: Observation of each case:for when you have no time left== |
Lets try casework and observe the cases. Notice that if the last roll is a <math>1</math>, then the only dice rolls may be <math>1-1-1-1</math>, which is only <math>1</math> possibility. Observe that if the last roll is <math>2</math>, then there are <math>4 = 1 + 3</math> possibilities. When the last roll is a <math>3</math>, there are <math>10 = 1 + 3 + 6</math> possibilities. Notice when the last roll is <math>n</math>, the number of cases is the sum of the first <math>n</math> positive triangular numbers. This is easily provable when observing the numbers of possibilities after assigning a value to the last and second to last rolls. | Lets try casework and observe the cases. Notice that if the last roll is a <math>1</math>, then the only dice rolls may be <math>1-1-1-1</math>, which is only <math>1</math> possibility. Observe that if the last roll is <math>2</math>, then there are <math>4 = 1 + 3</math> possibilities. When the last roll is a <math>3</math>, there are <math>10 = 1 + 3 + 6</math> possibilities. Notice when the last roll is <math>n</math>, the number of cases is the sum of the first <math>n</math> positive triangular numbers. This is easily provable when observing the numbers of possibilities after assigning a value to the last and second to last rolls. | ||
So there are a total of <math>1 + 1 + 3 + 1 + 3 + 6 + 1 + 3 + 6 + 10 + 1 + 3 + 6 + 10 + 15 + 1 + 3 + 6 + 10 + 15 + 21 = 126</math> possibilities. So the probability is <math>\frac{126}{6^4} = \frac{7}{72}</math> and <math> 7 + 72 = \boxed{079}</math>. ~skyscraper | So there are a total of <math>1 + 1 + 3 + 1 + 3 + 6 + 1 + 3 + 6 + 10 + 1 + 3 + 6 + 10 + 15 + 1 + 3 + 6 + 10 + 15 + 21 = 126</math> possibilities. So the probability is <math>\frac{126}{6^4} = \frac{7}{72}</math> and <math> 7 + 72 = \boxed{079}</math>. ~skyscraper |
Revision as of 23:57, 11 August 2019
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
Solutions
Solution 1
Recast the problem entirely as a block-walking problem. Call the respective dice . In the diagram below, the lowest
-coordinate at each of
,
,
, and
corresponds to the value of the roll.
The red path corresponds to the sequence of rolls . This establishes a one-to-one correspondence between valid dice roll sequences and block walking paths.
The solution to this problem is therefore . So the answer is
.
Solution 2
If we take any combination of four numbers, there is only one way to order them in a non-decreasing order. It suffices now to find the number of combinations for four numbers from . We can visualize this as taking the four dice and splitting them into 6 slots (each slot representing one of {1,2,3,4,5,6}), or dividing them amongst 5 separators. Thus, there are
outcomes of four dice. The solution is therefore
, and
.
Solution 3
Call the dice rolls . The difference between the
and
distinguishes the number of possible 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 4
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,
![$\frac{m}{n} = \frac{15 + 60 + 15 + 30 + 6}{6^4} = \frac{126}{6^4} = \frac{7}{72}$](http://latex.artofproblemsolving.com/f/a/7/fa7e76610f2e81a223ed2b61a6bcc7665e707692.png)
Solution 5
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 6
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
.
Solution 7 Recursion formula for the brain dead
If you're too tired to think about any of the above smart transformations of the problem, a recursion formula can be a robust way to the correct answer.
We just need to work out the valid cases for each roll. Denote by the number of valid cases in the
-th roll when the number
is rolled, for
and
. Then we have the following recursion formula:
The logic is that, if
is rolled, then the number of valid cases is the subtotal of valid cases in the preceding roll for the outcome of 1 to
. The recursion can be easily calculated by hand when
are put in columns side by side, given the fact that te numbers are smaller than 100.
Finally, the total number of cases is
and
Solution 8: Observation of each case:for when you have no time left
Lets try casework and observe the cases. Notice that if the last roll is a , then the only dice rolls may be
, which is only
possibility. Observe that if the last roll is
, then there are
possibilities. When the last roll is a
, there are
possibilities. Notice when the last roll is
, the number of cases is the sum of the first
positive triangular numbers. This is easily provable when observing the numbers of possibilities after assigning a value to the last and second to last rolls.
So there are a total of
possibilities. So the probability is
and
. ~skyscraper
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.