Question

求 $\{1, 2, 3, 4, 5, 6, 7, 8\}$ 的子集中，有多少个既不是 $\{1, 2, 3, 4, 5\}$ 的子集，也不是 $\{4, 5, 6, 7, 8\}$ 的子集。

Find the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}.$

答案

答案：196

知识点：子集容斥原理

难度评级：1890

解答：

总共有 $2^8 = 256$ 个子集。要排除的是包含在 $\{1,2,3,4,5\}$ 中的子集（有 $2^5 = 32$ 个），或包含在 $\{4,5,6,7,8\}$ 中的子集（也有 $32$ 个）。同时属于两者的子集正好是交集 $\{4, 5\}$ 的子集，共有 $2^2 = 4$ 个。

由容斥，失败的子集有 $32 + 32 - 4 = 60$ 个，因此满足要求的子集有 $256 - 60 = 196$ 个。

There are $2^8 = 256$ subsets in all. The ones to exclude are those contained in $\{1,2,3,4,5\}$ (there are $2^5 = 32$ ) or contained in $\{4,5,6,7,8\}$ (another $32$ ). A subset of both is exactly a subset of the intersection $\{4, 5\},$ and there are $2^2 = 4$ of those.

By inclusion-exclusion, $32 + 32 - 4 = 60$ subsets fail, so $256 - 60 = 196$ subsets have the required property.

2017 AIME II 第 1 题

答案：196

难度评级：1890

解答：

其他年份的第 1 题