Principio de la Suma

Teoría

El Principio de la Suma es un concepto fundamental en combinatoria que usas para contar el número total de resultados cuando tienes opciones distintas y mutuamente excluyentes. Dice que si puedes realizar una tarea de una de dos formas, y la primera tiene $m$ posibilidades mientras que la segunda tiene $n$ posibilidades, y —esto es súper importante— estas posibilidades no pueden ocurrir al mismo tiempo, entonces el número total de formas de realizar la tarea es $m + n$. En términos de conjuntos, este principio asegura que el tamaño de la unión de conjuntos ajenos es la suma de sus tamaños individuales.

Esta técnica es la base del "Casework" (o Análisis de Casos), una estrategia vital en competencias de matemáticas como el AMC 8 y el AMC 10. Cuando un problema es muy complejo para resolverlo con una sola fórmula (como permutaciones o combinaciones) debido a diferentes restricciones, lo que haces es dividir el problema en escenarios (casos) más pequeños, manejables y ajenos. Al calcular el número de posibilidades para cada caso específico y sumarlas, llegas al total.

La intuición detrás del Principio de la Suma es la de partir un todo en partes. Si tienes una colección de objetos y los separas en botes distintos de modo que ningún objeto esté en más de un bote, el número total de objetos es simplemente la suma de los conteos de cada bote. Para dominar este principio, necesitas poder identificar correctamente cuándo los eventos son ajenos (mutuamente excluyentes); si hay un traslape entre los casos, aplicar el Principio de la Suma directamente hará que cuentes de más, y entonces necesitarías usar el Principio de Inclusión-Exclusión.

Fórmulas Clave

Principio de la Suma Básico Para dos conjuntos finitos $A$ y $B$, si son ajenos (es decir, $A \cap B = \emptyset$), entonces: $$ |A \cup B| = |A| + |B| $$

Principio de la Suma General Para una colección finita de conjuntos $S_1, S_2, \dots, S_k$ que son ajenos por pares (es decir, $S_i \cap S_j = \emptyset$ para todo $i \neq j$), la cardinalidad de su unión es la suma de sus cardinalidades: $$ \left| \bigcup_{i=1}^k S_i \right| = \sum_{i=1}^k |S_i| = |S_1| + |S_2| + \dots + |S_k| $$

Relación con Inclusión-Exclusión Si los conjuntos $A$ y $B$ no son ajenos, ajustas el Principio de la Suma restando el traslape: $$ |A \cup B| = |A| + |B| - |A \cap B| $$

Demostración

Teorema: Si $A$ y $B$ son conjuntos finitos ajenos con $|A| = m$ y $|B| = n$, entonces $|A \cup B| = m + n$.

Demostración: Aquí te basas en la definición de cardinalidad. Un conjunto $S$ tiene cardinalidad $k$ si y solo si existe una biyección (un mapeo uno a uno y sobre) del conjunto ${1, 2, \dots, k}$ a $S$.

1. Define los mapeos para A y B: Como $|A| = m$, existe una biyección $f: {1, 2, \dots, m} \to A$. Como $|B| = n$, existe una biyección $g: {1, 2, \dots, n} \to B$.

2. Construye un mapeo para la unión: Lo que quieres mostrar es que hay una biyección $h: {1, 2, \dots, m+n} \to A \cup B$. Define la función $h(x)$ de esta forma: $$ h(x) = \begin{cases} f(x) & \text{if } 1 \le x \le m \ g(x - m) & \text{if } m+1 \le x \le m+n \end{cases} $$

3. Verifica que $h$ sea una biyección:

   • Inyectividad (Uno a uno):

     • Si $x, y \le m$ y $h(x) = h(y)$, entonces $f(x) = f(y)$, lo que implica que $x=y$ porque $f$ es biyectiva.
     • Si $x, y > m$ y $h(x) = h(y)$, entonces $g(x-m) = g(y-m)$, lo que implica que $x-m = y-m \implies x=y$ porque $g$ es biyectiva.
     • Si $x \le m$ y $y > m$, entonces $h(x) \in A$ y $h(y) \in B$. Como $A$ y $B$ son ajenos ($A \cap B = \emptyset$), $h(x) \neq h(y)$. Por lo tanto, $h$ es inyectiva.

   • Suprayectividad (Sobre):

     • Toma cualquier elemento $y$ en $A \cup B$.
     • Si $y \in A$, existe un $x \in {1, \dots, m}$ tal que $f(x) = y$. Así que $h(x) = y$.
     • Si $y \in B$, existe un $z \in {1, \dots, n}$ tal que $g(z) = y$. Si tomas $x = z + m$, entonces $m+1 \le x \le m+n$, y $h(x) = g(x-m) = g(z) = y$. Por lo tanto, $h$ es suprayectiva.

4. Conclusión: Como existe una biyección de ${1, 2, \dots, m+n}$ a $A \cup B$, la cardinalidad de $A \cup B$ es exactamente $m + n$.

$\square$