Question

十把椅子围成一圈。求这些椅子的子集中，包含至少三把相邻椅子的子集个数。

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs.

答案

答案：581

知识点：环形排列子集容斥原理

难度评级：2760

解答：

全部 $10$ 把椅子的子集符合条件；先数其他子集。对每个长度至少为三的极大连续选中段，定位其顺时针起点。这样的子集必含一个连续四椅块，形如空-选-选-选。这个块有 $10$ 个位置，其余 $6$ 把椅子任意选择，给出 $10 \cdot 2^6 = 640$ 次计数。

每个子集被计数的次数等于其长度至少为 $3$ 的极大连续段数。两个这样的连续段至少需要 $3 + 3$ 把选中椅子和两个空隙，所以不可能有三段；恰有两段的子集被计数两次。要有两段，放置两个不相交的空-选-选-选块：有 $\frac{10 \cdot 3}{2} = 15$ 种方法（第二个块在剩余 $6$ 把椅子中有 $3$ 个位置），最后 $2$ 把椅子任意选择，因此有 $15 \cdot 2^2 = 60$ 个这样的子集。

总数为 $1 + 640 - 60 = 581$ 。

The full set of $10$ chairs qualifies; count the others by locating each maximal run of at least three adjacent chosen chairs at its clockwise start. Any such subset contains a block of four consecutive chairs that is empty-chosen-chosen-chosen. There are $10$ positions for this block, and the remaining $6$ chairs are free, giving $10 \cdot 2^6 = 640.$

This counts once for each maximal run of length at least $3.$ Two such runs require at least $3 + 3$ chosen chairs plus two gaps, so three runs are impossible, and subsets with exactly two runs are counted twice. To have two runs, place two disjoint empty-chosen-chosen-chosen blocks: $\frac{10 \cdot 3}{2} = 15$ ways (the second block fits in $3$ positions among the remaining $6$ chairs), with the last $2$ chairs free, for $15 \cdot 2^2 = 60$ subsets.

The total is $1 + 640 - 60 = 581.$

2014 AIME II 第 9 题

答案：581

难度评级：2760

解答：

其他年份的第 9 题