HMMT 二月 2002 · ADV 赛 · 第 5 题
HMMT February 2002 — ADV Round — Problem 5
题目详情
- Determine the number of subsets S of { 1 , 2 , 3 , . . . , 10 } with the following property: there exist integers a < b < c with a ∈ S, b / ∈ S, c ∈ S .
解析
- Determine the number of subsets S of { 1 , 2 , 3 , . . . , 10 } with the following property: there exist integers a < b < c with a ∈ S, b / ∈ S, c ∈ S . 10 Solution: 968 There are 2 = 1024 subsets of { 1 , 2 , . . . , 10 } altogether. Any subset without the specified property must be either the empty set or a block of consecutive integers. To specify a block of consecutive integers, we either have just one element (10 choices) or a ( ) 10 pair of distinct endpoints ( = 45 choices). So the number of sets with our property is 2 1024 − (1 + 10 + 45) = 968.