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

2010 AIME I (Problems • Answer Key • Resources)
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

Page

Toolbox

Search

2010 AIME I Problems/Problem 7

Problem

Solution

See Also