Problem:
Define an ordered triple (A,B,C) of sets to be minimally intersecting if ∣A∩B∣=∣B∩C∣=∣C∩A∣=1 and A∩B∩C=∅. 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 S={1,2,3,4,5,6,7}. If (A,B,C) is a minimally intersecting ordered triple of subsets of S, then there exist distinct x,y,z∈S such that A∩B= {x},B∩C={y}, and A∩C={z}. There are 7⋅6⋅5 ways to assign values to x,y,z. For each of the four remaining elements of S, there are four possibilities, namely that either the element belongs to exactly one of the three sets A,B, or C, or it belongs to none of the three sets. Thus there are a total of 7⋅6⋅5⋅44 minimally intersecting ordered triples of sets in which each set in each triple is a subset of S. Thus N=7⋅6⋅5⋅44= 210⋅256=53760, and the requested remainder is 760 .
The problems on this page are the property of the MAA's American Mathematics Competitions