2001 AIME I Problem 6

Question

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

\frac{m}{n},

where

m

and

n

are relatively prime positive integers. Find

m + n.

Answer

Answer: 79

Concepts:basic probability stars and bars bijection

Difficulty rating: 2230

Small hint:

Every collection of four values (with repeats allowed) can be arranged in exactly one non-decreasing order

Big hint:

Count multisets of size

4

from

\{1, \ldots, 6\}

by stars and bars:

\binom{9}{4}

Solution:

The rolls must form a non-decreasing sequence. Every multiset of four values from

\{1, \ldots, 6\}

can be arranged in non-decreasing order in exactly one way, so the number of successful outcomes equals the number of such multisets. By stars and bars (4 stars and

5

dividers), that count is

\binom{9}{4} = 126.

The probability is

\frac{126}{6^4} = \frac{126}{1296} = \frac{7}{72},

so

m + n = 7 + 72 = 79.