Maths Olympiad Prep

Library / /309 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

Determine the number of sequences of sets S1,S2,,S999S_{1}, S_{2}, \ldots, S_{999} such that S1S2S999{1,2,,999}S_{1} \subseteq S_{2} \subseteq \cdots \subseteq S_{999} \subseteq\{1,2, \ldots, 999\} Here ABA \subseteq B means that all elements of AA are also elements of BB.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The idea is to look at each element individually, rather than each subset. For each k{1,2,,999}k \in\{1,2, \ldots, 999\}, there are 1000 choices for the first subset in the chain that contains kk. This count includes the possibility that kk doesn't appear in any of the subsets. If SiS_{i} is the first subset containing kk, for some i{1,2,,999}i \in\{1,2, \ldots, 999\}, then kk is also in SjS_{j}, for all i<j999i<j \leq 999. As a result, picking the first subset that contains kk uniquely determines the appearance of kk in all the subsets. It follows that there are 10009991000^{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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.