Problem:
A board has spaces in a row, which can be filled with numbers. The sides of a fair, -sided die are numbered through . David rolls the die times. After each roll, he randomly chooses an empty spot to write the number shown on the die. What is the probability that the numbers on the board form a strictly increasing sequence when read from left to right?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
David chooses the spots at random without looking at the numbers, so the four rolled numbers end up on the board in a uniformly random order, independent of what the numbers are.
Step 1: The numbers must be distinct. A strictly increasing sequence has no repeated values. The probability that the four rolls are all different is
Step 2: The order must be correct. Given four distinct numbers, exactly one of the equally likely orders is increasing.
Therefore the probability is
Alternative count. The increasing outcome is determined by choosing a set of distinct values, in ways; each such board appears with probability , giving .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions