2010 AIME I Problems/Problem 7

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}$.

See Also

2010 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 6
Followed by
Problem 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png