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 bein 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.
• Case: x ∈ A but x / ∈ A . Then the only other sets that x could be in are A , A , A , and x 1
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