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: thereexist 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 .
Solution: 968 There are 2 = 1024 subsets of { 1 , 2 , . . . , 10 } altogether. Any subset 10
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
( )
pair of distinct endpoints ( = 45 choices). So the number of sets with our property is 10
1024 − (1 + 10 + 45) = 968.2