Maths Olympiad Prep

Library / /437 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Determine the number of ways to select a sequence of 8 sets A1,A2,,A8A_{1}, A_{2}, \ldots, A_{8}, such that each is a subset (possibly empty) of \{1,2\}, and AmA_{m} contains AnA_{n} if mm divides nn.

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

Solution

Consider an arbitrary x{1,2}x \in\{1,2\}, and let us consider the number of ways for xx to be in some of the sets so that the constraints are satisfied. We divide into a few cases: - Case: xA1x \notin A_{1}. Then xx cannot be in any of the sets. So there is one possibility. - Case: xA1x \in A_{1} but xA2x \notin A_{2}. Then the only other sets that xx could be in are A3,A5,A7A_{3}, A_{5}, A_{7}, and xx could be in some collection of them. There are 8 possibilities in this case. - Case: xA2x \in A_{2}. Then xA1x \in A_{1} automatically. There are 4 independent choices to be make here: (1) whether xA5;(2)x \in A_{5} ;(2) whether xA7;(3)x \in A_{7} ;(3) whether xA3x \in A_{3}, and if yes, whether xA6x \in A_{6}; (4) whether xA4x \in A_{4}, and if yes, whether xA8x \in A_{8}. There are 2×2×3×3=362 \times 2 \times 3 \times 3=36 choices here. Therefore, there are 1+8+36=451+8+36=45 ways to place xx into some of the sets. Since the choices for x=1x=1 and x=2x=2 are made independently, we see that the total number of possibilities is 452=202545^{2}=2025.

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.