Question

Se dice que una terna ordenada $(\mathcal{A}, \mathcal{B}, \mathcal{C})$ de conjuntos es mínimamente intersecante si $|\mathcal{A} \cap \mathcal{B}| = |\mathcal{B} \cap \mathcal{C}| = |\mathcal{C} \cap \mathcal{A}| = 1$ y $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset.$ Por ejemplo, $(\{1, 2\}, \{2, 3\}, \{1, 3, 4\})$ es una terna mínimamente intersecante. Sea $N$ el número de ternas ordenadas mínimamente intersecantes de conjuntos para las que cada conjunto es un subconjunto de $\{1, 2, 3, 4, 5, 6, 7\}.$ Halle el residuo cuando $N$ se divide entre $1000.$

Nota: $|\mathcal{S}|$ representa el número de elementos en el conjunto $\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}.$

Respuesta

Solución:

Escriba $\mathcal{A} \cap \mathcal{B} = \{x\},$ $\mathcal{B} \cap \mathcal{C} = \{y\},$ y $\mathcal{C} \cap \mathcal{A} = \{z\}.$ Como $\mathcal{A} \cap \mathcal{B} \cap \mathcal{C} = \emptyset,$ los elementos $x,$ $y,$ $z$ son distintos, y pueden elegirse de $7 \cdot 6 \cdot 5 = 210$ maneras.

Cada uno de los $4$ elementos restantes no debe crear más intersecciones por pares, así que puede pertenecer a exactamente uno de $\mathcal{A},$ $\mathcal{B},$ $\mathcal{C},$ o a ninguno de ellos: $4$ opciones cada uno, para $4^4 = 256$ asignaciones.

Por lo tanto, $N = 210 \cdot 256 = 53760,$ y el residuo al dividir entre $1000$ es $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 Problema 7

Solución:

El Problema 7 en otros años