Track / Stage 5 / 44 of 400 #644 of 1964

Problem 644

AIME late

Combinatorics Difficulty 5.1 Find the answer

$A_{1}, A_{2}, \cdots, A_{t}$ are all $r$ -sets, $X=\bigcup_{i=1}^{t} A_{i}$ , find $\min |X|$ . Here the minimum is over all $A_{1}, A_{2}, \cdots, A_{i}$ of $|X|$ .

Your answer

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

Official solution

19. Let $n$ be the smallest integer satisfying $C_{n}^{r} \geqslant t$ . On one hand, $A_{1}, A_{2}, \cdots, A_{4}$ are all $r$ -element subsets of $X$ , so $t \leqslant C_{|X|}^{r}$ . Therefore, $|X| \geqslant n$ .

On the other hand, for any $n$ -element set $X$ , there are $C_{n} \geqslant t$ $r$ -element subsets. Choose any $t$ of them. Let their union be $Y$ , then by the above, $|Y| \geqslant n$ , hence $Y=X$ . Therefore, $X$ is the union of the $t$ chosen $r$ -element subsets.
Thus, the required minimum value is $n$ .

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