Library / /582 of 740

, 2014

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:
Determine the number of sequences of sets $S_{1}, S_{2}, \ldots, S_{999}$ such that
$S_{1} \subseteq S_{2} \subseteq \cdots \subseteq S_{999} \subseteq \{1,2, \ldots, 999\}$
Here $A \subseteq B$ means that all elements of $A$ are also elements of $B$ .

Solution

Solution:
$10^{2997}$ OR $1000^{999}$ The idea is to look at each element individually, rather than each subset. For each $k \in \{1,2, \ldots, 999\}$ , there are $1000$ choices for the first subset in the chain that contains $k$ . This count includes the possibility that $k$ doesn't appear in any of the subsets. If $S_{i}$ is the first subset containing $k$ , for some $i \in \{1,2, \ldots, 999\}$ , then $k$ is also in $S_{j}$ , for all $i<j \leq 999$ . As a result, picking the first subset that contains $k$ uniquely determines the appearance of $k$ in all the subsets. It follows that there are $1000^{999}$ such subset chains.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.