Track / Stage 5 / 4 of 400 #604 of 1964

Problem 604

AIME late

Combinatorics Difficulty 5.0 Find the answer

$\frac{1}{2} n(n+1)$ distinct numbers are randomly arranged in a triangle:

Let $M_{\mathrm{k}}$ be the maximum number in the $k$ -th row (counting from the top), find the probability that $M_{1}<M_{2}<M_{3}<\cdots<M_{\mathrm{n}}$ holds.

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

2. Let the required probability be $p_{\mathrm{n}}$ , obviously, $p_{1}=1$ , $p_{2}=2 / 3$ .

Since the largest number must appear in the last row to satisfy the inequality described in the problem. The probability of this situation occurring is
$\frac{n}{\frac{1}{2} n(n+1)}=\frac{2}{n+1} .$

Therefore,
$p_{n}=\frac{2}{n+1} p_{n-1}=\cdots=\frac{2^{n}}{(n+1)!} \quad(n \geqslant 2) .$

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.