HMMT 二月 2008 · COMB 赛 · 第 8 题

HMMT February 2008 — COMB Round — Problem 8

[ 6 ] Determine the number of ways to select a sequence of 8 sets A , A , . . . , A , such that each is a 1 2 8 subset (possibly empty) of { 1 , 2 } , and A contains A if m divides n . m n

解析

[ 6 ] Determine the number of ways to select a sequence of 8 sets A , A , . . . , A , such that each is a 1 2 8 subset (possibly empty) of { 1 , 2 } , and A contains A if m divides n . m n Answer: 2025 Consider an arbitrary x ∈ { 1 , 2 } , and let us consider the number of ways for x to be in some of the sets so that the constraints are satisfied. We divide into a few cases: • Case: x / ∈ A . Then x cannot be in any of the sets. So there is one possibility. 1 • Case: x ∈ A but x / ∈ A . Then the only other sets that x could be in are A , A , A , and x 1 2 3 5 7 could be in some collection of them. There are 8 possibilities in this case. • Case: x ∈ A . Then x ∈ A automatically. There are 4 independent choices to be make here: 2 1