1993 AIME 第 8 题

Question

设

S

是一个含有六个元素的集合。从

S

中选取两个不一定互不相同的子集，使它们的并集为

S

，共有多少种不同的选法？选取顺序不计；例如，子集对

\{a,c\}

、

\{b,c,d,e,f\}

与子集对

\{b,c,d,e,f\}

、

\{a,c\}

表示同一种选法。

Let

S

be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of

S

so that the union of the two subsets is

S?

The order of selection does not matter; for example, the pair of subsets

\{a,c\},

\{b,c,d,e,f\}

represents the same selection as the pair

\{b,c,d,e,f\},

\{a,c\}.

答案

答案：365

知识点：伯恩赛德引理乘法原理子集

难度评级：1930

小提示：

对于有序子集对，每个元素可以只属于第一个子集、只属于第二个子集，或同时属于两者

For an ordered pair, each element can lie in the first subset only, the second only, or both

大提示：

交换两个子集时，找出唯一保持不变的有序子集对

When the two subsets are swapped, identify the one ordered pair that remains fixed

解答：

对于有序子集对

(A,B)

，若

A\cup B=S

，则每个元素有三种归属方式：只属于

A

、只属于

B

，或同时属于两者。因此共有

3^6=729

个有序子集对。交换

A

与

B

时，只有

A=B=S

这一对子集保持不变。所以无序子集对的数目为

\frac{729+1}{2}=365\text{。}

For an ordered pair

(A,B)

with

A\cup B=S,

each element has three possible memberships:

A

only,

B

only, or both. This gives

3^6=729

ordered pairs. Swapping

A

and

B

fixes only the pair

A=B=S.

Therefore the number of unordered pairs is

\frac{729+1}{2}=365.

1993 AIME 第 8 题

答案：365

难度评级：1930

小提示：

大提示：

解答：

其他年份的第 8 题