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

小提示：

除全集外，按顺时针找到一把空椅子，后面紧接着三把属于该子集的椅子

Count subsets other than the full set by locating an empty chair followed clockwise by three chairs of the subset

大提示：

每个这样的空-选-选-选模式让剩下六把椅子任意选择，共有 $2^6$ 种；再减去含有两段相互分离的长度至少为三的连续段而被重复计算的子集。

Each such empty-full-full-full pattern leaves $2^6$ choices for the remaining chairs; subtract the double-counted subsets containing two separate runs of three or more

解答：

全部 $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 题