A fair die is rolled four times. What is the probability that each of the final three rolls is at least as large as the roll preceding it?
This question is from the AIME 2001.
I am looking for a solution that does not use brute-force methods.
Considering a starting point at the number $1$, the problem can be formulated as finding the number of integer tuples $(x_1,x_2,x_3,x_4)$ such that:
- $x_1\ge0,x_2\ge0,x_3\ge_0,x_4\ge0$
- $x_1+x_2+x_3+x_4\le5$
Each element $x_i$ in a tuple represents the increment in throwing the die for the $i-th$ time over what was obtained on the $(i-1)-st$ throw. We consider the $0-th$ throw to be $1$. Hence, there is a one-to-one mapping between all qualifying dice throws and all tuples that meet the stated conditions.
I know the total number of possible dice rolls is $6^4$ but am unsure how to count the number of tuples.
The brute-force method is to simply count the number of distinct solutions to each of $x_1+x_2+x_3+x_4=0,\quad x_1+x_2+x_3+x_4=1,\ldots$ by listing all ways of making up the sums accounting for permutations. For example:
$$\underline{x_1+x_2+x_3+x_4=2} \\
\begin{array}{crl}
(0,0,0,2) & 4 & \text{perms} \\
(0,0,1,1) & 6 & \text{perms} \\
\text{total} & 10
\end{array}$$
But I think there must be a more elegant way.
Best Answer
Add a fifth variable, $x_5$, to take up the slack, and count the solutions in non-negative integers to $$x_1+x_2+x_3+x_4+x_5=5\;;$$ by the standard stars and bars argument this is $\binom{5+5-1}{5-1}=\binom94=126$.