Question

若集合的有序三元组 $(\mathcal{A}, \mathcal{B}, \mathcal{C})$ 满足 $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{B} \cap \mathcal{C}| = |\mathcal{C} \cap \mathcal{A}| = 1$ ，且 $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset$ 。则称它为极小相交的。例如， $(\{1, 2\}, \{2, 3\}, \{1, 3, 4\})$ 是一个极小相交三元组。设 $N$ 为这样的极小相交有序集合三元组的个数，其中每个集合都是 $\{1, 2, 3, 4, 5, 6, 7\}$ 的子集。求 $N$ 除以 $1000$ 的余数。

注： $|\mathcal{S}|$ 表示集合 $\mathcal{S}$ 中元素的个数。

Define an ordered triple $(\mathcal{A}, \mathcal{B}, \mathcal{C})$ of sets to be minimally intersecting if $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{B} \cap \mathcal{C}| = |\mathcal{C} \cap \mathcal{A}| = 1$ and $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset.$ For example, $(\{1, 2\}, \{2, 3\}, \{1, 3, 4\})$ is a minimally intersecting triple. Let $N$ be the number of minimally intersecting ordered triples of sets for which each set is a subset of $\{1, 2, 3, 4, 5, 6, 7\}.$ Find the remainder when $N$ is divided by $1000.$

Note: $|\mathcal{S}|$ represents the number of elements in the set $\mathcal{S}.$

答案

答案：760

知识点：韦恩图乘法原理子集

难度评级：2510

解答：

记 $\mathcal{A} \cap \mathcal{B} = \{x\}$ ， $\mathcal{B} \cap \mathcal{C} = \{y\}$ ， $\mathcal{C} \cap \mathcal{A} = \{z\}$ 。由于 $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset$ ，元素 $x$ 、 $y$ 、 $z$ 互不相同，并且可用 $7 \cdot 6 \cdot 5 = 210$ 种方式选出。

剩下 $4$ 个元素都不能产生额外的两两交集，所以每个元素可以只属于 $\mathcal{A}$ 、 $\mathcal{B}$ 、 $\mathcal{C}$ 中的一个，或者都不属于：每个有 $4$ 种选择，共 $4^4 = 256$ 种分配。

因此 $N = 210 \cdot 256 = 53760$ ，除以 $1000$ 的余数为 $760$ 。

Write $\mathcal{A} \cap \mathcal{B} = \{x\},$ $\mathcal{B} \cap \mathcal{C} = \{y\},$ and $\mathcal{C} \cap \mathcal{A} = \{z\}.$ Since $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset,$ the elements $x,$ $y,$ $z$ are distinct, and they can be chosen in $7 \cdot 6 \cdot 5 = 210$ ways.

Each of the remaining $4$ elements must not create any further pairwise intersections, so it can belong to exactly one of $\mathcal{A},$ $\mathcal{B},$ $\mathcal{C},$ or to none of them: $4$ choices each, for $4^4 = 256$ assignments.

Hence $N = 210 \cdot 256 = 53760,$ and the remainder upon division by $1000$ is $760.$

2010 AIME I 第 7 题

答案：760

难度评级：2510

解答：

其他年份的第 7 题