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 .
Solution:
Any particular outcome of the four rolls has probability . Given the values of four rolls, there is exactly one order that satisfies the requirement. It therefore suffices to count all the sets of values that could be produced by four rolls, allowing duplicate values. This is equivalent to counting the number of ways to put four balls into six boxes labeled through . By thinking of balls and dividers to separate the six boxes, this can be seen to be . The requested probability is thus , so .
Let , and be the sequence of values rolled, and consider the difference between the last and the first: If , then there is possibility for and , and possibilities for and . If , then there are possibilities for and , and possibilities for and . In general, if , then there are possibilities for and , while the number of possibilities for and is the same as the number of sets of elements, with repetition allowed, that can be chosen from a set of elements. This is equal to the number of ways to put balls in boxes, or . Thus there are sequences of the type requested, so the probability is , and .
Define an acceptable sequence to be one in which each element is between and and is at least as large as the preceding element. Let be the number of acceptable sequences of length beginning with . Then, for , and is equal to the number of acceptable sequences of length that begin with a value at least as large as . That is, . Use this relationship to produce the table shown below. The requested probability is or .
The problems on this page are the property of the MAA's American Mathematics Competitions