Track / Stage 4 / 268 of 340 #1008 of 2444

Problem 1008

AMC 12 late, AIME early

Combinatorics Difficulty 4.9 Prove it Taiwan IMO Selection Camp · Taiwan

From the set $S=\{1,2,3, ..., 2024\}$ , take out 1000 numbers to form a subset $T$ with 1000 elements, and let the minimum element of $T$ be $k$ . Find the expected value of $k$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $M$ be the expected value sought, then we have:
$\begin{aligned} \binom{2024}{1000} M &= 1 \cdot \binom{2023}{999} + 2 \cdot \binom{2022}{999} + 3 \cdot \binom{2021}{999} + \cdots + 1025 \cdot \binom{999}{999} \\ &= \sum_{a+b=1025} \binom{a}{1} \binom{b+999}{999} \\ &= \binom{1025+999+1}{1+999+1} \\ &= \binom{2025}{1001} \\ M &= \frac{2025}{1001} \end{aligned}$

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty, ordering) added by this project.