Conteo por Casos Disjuntos

Teoría

Contar por casos disjuntos, que formalmente se conoce como el Principio de la Suma o la Regla de la Suma, es una estrategia fundamental en combinatoria que usas cuando no puedes resolver un problema de conteo complejo con un solo cálculo. En lugar de intentar contar todas las posibilidades de un jalón, divides el problema en escenarios más pequeños y manejables llamados "casos". El requisito crítico para esta técnica es que los casos deben ser disjuntos (mutuamente excluyentes) y exhaustivos. Esto significa que ningún resultado puede pertenecer a más de un caso, y cada resultado posible debe pertenecer al menos a un caso.

Esta técnica es súper importante en matemáticas de competencia como el AMC 8 porque transforma restricciones difíciles en subproblemas más simples. Por ejemplo, si estás contando cuántos enteros tienen una propiedad específica, puede que sea difícil encontrar una sola fórmula. Pero si separas los enteros según su número de dígitos (Caso 1: 1 dígito, Caso 2: 2 dígitos, etc.) o por su último dígito, el conteo se vuelve muy fácil para cada caso específico.

El truco principal al aplicar este método es definir los casos basándote en una propiedad que divida estrictamente el conjunto de todas las posibilidades. Si los casos se enciman (o sea, si un resultado cae en el Caso A y en el Caso B), simplemente sumar las cuentas hará que cuentes cosas de más. Si los casos no cubren todas las posibilidades, te van a faltar elementos. Por eso, para aplicar bien el conteo por casos disjuntos, tienes que definir con cuidado los criterios que separan los casos para asegurar que formen una partición de todo el espacio muestral.

Fórmulas Clave

El Principio de la Suma (Dos Conjuntos) Si $A$ y $B$ son dos conjuntos finitos que son disjuntos (lo que significa que no tienen elementos en común, o $A \cap B = \emptyset$), entonces el número de elementos en su unión es la suma del número de elementos de cada conjunto: $$|A \cup B| = |A| + |B|$$

El Principio de la Suma General Si divides un conjunto finito $S$ en $k$ subconjuntos disjuntos $S_1, S_2, \dots, S_k$, de tal forma que:

1. Disjuntos por pares: $S_i \cap S_j = \emptyset$ para todo $i \neq j$
2. Exhaustivos: $S_1 \cup S_2 \cup \dots \cup S_k = S$

Entonces el número total de elementos en $S$ es la suma del número de elementos de cada subconjunto: $$|S| = |S_1| + |S_2| + \dots + |S_k| = \sum_{i=1}^{k} |S_i|$$

Demostración

Teorema: Para dos conjuntos finitos disjuntos $A$ y $B$, $|A \cup B| = |A| + |B|$.

Demostración: Supón que $|A| = m$ y $|B| = n$, donde $m$ y $n$ son enteros no negativos. Por la definición de cardinalidad, existen biyecciones (correspondencias uno a uno) de los conjuntos a segmentos estándar de los números naturales.

1. Toma una biyección $f: A \to {1, 2, \dots, m}$. Esto básicamente etiqueta los elementos de $A$ como $a_1, a_2, \dots, a_m$.
2. Toma una biyección $g: B \to {1, 2, \dots, n}$. Esto etiqueta los elementos de $B$ como $b_1, b_2, \dots, b_n$.

Lo que quieres es encontrar la cardinalidad de $A \cup B$. Para lograrlo, hay que construir una biyección $h$ de $A \cup B$ al conjunto ${1, 2, \dots, m+n}$.

Define la función $h: A \cup B \to {1, 2, \dots, m+n}$ de esta manera: $$ h(x) = \begin{cases} f(x) & \text{if } x \in A \ g(x) + m & \text{if } x \in B \end{cases} $$

Justificación de que $h$ es una biyección:

• Bien definida: Como $A$ y $B$ son disjuntos ($A \cap B = \emptyset$), cada elemento $x \in A \cup B$ pertenece exactamente a uno de los conjuntos. Por lo tanto, no hay ambigüedad al definir $h(x)$.
• Inyectiva (Uno a uno):
  • Si tienes elementos distintos $x, y$ que están en $A$, entonces $h(x) \neq h(y)$ porque $f$ es una biyección.
  • Si tienes elementos distintos $x, y$ que están en $B$, entonces $h(x) \neq h(y)$ porque $g$ es una biyección (sumar $m$ mantiene la desigualdad).
  • Si $x \in A$ y $y \in B$, entonces $h(x) \in {1, \dots, m}$ y $h(y) \in {m+1, \dots, m+n}$. Como estos rangos no se enciman, $h(x) \neq h(y)$.
• Suprayectiva (Sobre):
  • La imagen de $A$ bajo $h$ cubre ${1, \dots, m}$.
  • La imagen de $B$ bajo $h$ cubre ${m+1, \dots, m+n}$.
  • Por lo tanto, la imagen de $A \cup B$ es exactamente ${1, \dots, m+n}$.

Como existe una biyección entre $A \cup B$ y el conjunto ${1, 2, \dots, m+n}$, puedes concluir que: $$|A \cup B| = m + n = |A| + |B|$$ $\square$