Maths Olympiad Prep

Library / /182 of 377

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
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}\{1,2\}, and AmA_{m} contains AnA_{n} if mm divides nn.

Solution

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 xA5x \in A_{5}; (2) whether xA7x \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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.