Determine the number of sequences of sets such that Here means that all elements of are also elements of .
Solution
The idea is to look at each element individually, rather than each subset. For each , there are 1000 choices for the first subset in the chain that contains . This count includes the possibility that doesn't appear in any of the subsets. If is the first subset containing , for some , then is also in , for all . As a result, picking the first subset that contains uniquely determines the appearance of in all the subsets. It follows that there are 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.