Determine the number of ways to select a sequence of 8 sets , such that each is a subset (possibly empty) of \{1,2\}, and contains if divides .
Solution
Consider an arbitrary , and let us consider the number of ways for to be in some of the sets so that the constraints are satisfied. We divide into a few cases: - Case: . Then cannot be in any of the sets. So there is one possibility. - Case: but . Then the only other sets that could be in are , and could be in some collection of them. There are 8 possibilities in this case. - Case: . Then automatically. There are 4 independent choices to be make here: (1) whether whether whether , and if yes, whether ; (4) whether , and if yes, whether . There are choices here. Therefore, there are ways to place into some of the sets. Since the choices for and are made independently, we see that the total number of possibilities is .
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.