AIME 2010 I · 第 7 题

AIME 2010 I — Problem 7

专题: Contest Math
难度: L4
来源: AIME

题目详情

Problem

Define an ordered triple $(A, B, C)$ of sets to be minimally intersecting if $|A \cap B| = |B \cap C| = |C \cap A| = 1$ and $A \cap B \cap 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: $|S|$ represents the number of elements in the set $S$ .

解析

Solution

Let each pair of two sets have one element in common. Label the common elements as $x$ , $y$ , $z$ . Set $A$ will have elements $x$ and $y$ , set $B$ will have $y$ and $z$ , and set $C$ will have $x$ and $z$ . There are $7 \cdot 6 \cdot 5 = 210$ ways to choose values of $x$ , $y$ and $z$ . There are $4$ unpicked numbers, and each number can either go in the first set, second set, third set, or none of them. Since we have $4$ choices for each of $4$ numbers, that gives us $4^4 = 256$ .

Finally, $256 \cdot 210 = 53760$ , so the answer is $\fbox{760}$ .