Lección 1.2: Principio de adición y multiplicación — Espinoza Olimpiadas

La pregunta del menú

Un restaurante ofrece 3 sopas, 4 platos de fondo y 2 postres. ¿Cuántas comidas distintas puede armar un cliente que elige exactamente una opción de cada categoría? Antes de leer la respuesta, intenta contarlo tú mismo.

Podrías listar: sopa 1 con fondo 1 y postre 1, sopa 1 con fondo 1 y postre 2, sopa 1 con fondo 2 y postre 1, ... La lista crece rápido. Pero hay una forma mucho más eficiente de contar.

La respuesta es $3 \times 4 \times 2 = 24$ . Esta multiplicación no es una coincidencia: es el principio multiplicativo, la herramienta más fundamental del conteo combinatorio.

El principio multiplicativo: por qué "y" se convierte en "×"

Formalmente: si una tarea se puede descomponer en dos etapas independientes, donde la primera etapa se puede realizar de $m$ maneras y la segunda de $n$ maneras (sin importar cómo se hizo la primera), entonces la tarea completa se puede realizar de $m \times n$ maneras.

La palabra clave es independiente: la cantidad de opciones en la segunda etapa no cambia según la elección de la primera. En el menú, los 4 fondos disponibles no dependen de qué sopa elegiste. Por eso se multiplica.

Para $k$ etapas con $n_1, n_2, \ldots, n_k$ opciones cada una (todas independientes), el total es $n_1 \times n_2 \times \cdots \times n_k$ . Cada vez que el enunciado dice "elige A y luego elige B", piensa en multiplicar.

n_1 \times n_2 \times \cdots \times n_k

Rutas, contraseñas y códigos

Problema de rutas: Para ir de la ciudad $A$ a la ciudad $C$ pasando por $B$ , hay 4 caminos de $A$ a $B$ y 3 caminos de $B$ a $C$ . ¿Cuántas rutas distintas hay de $A$ a $C$ ? Como primero recorres un segmento y luego el otro, el total es $4 \times 3 = 12$ rutas.

Contraseñas: Una contraseña consiste en 3 letras (del abecedario de 27 letras) seguidas de 2 dígitos (del 0 al 9), donde se permite repetición. El número de contraseñas posibles es $27^3 \times 10^2 = 19\,683 \times 100 = 1\,968\,300$ . Si no se permite repetición de letras y tampoco de dígitos, sería $27 \times 26 \times 25 \times 10 \times 9 = 1\,579\,500$ .

Placas de vehículos: Si una placa tiene 3 letras seguidas de 3 dígitos (sin repetición de letras, sin restricción en dígitos), el total es $26 \times 25 \times 24 \times 10 \times 10 \times 10 = 15\,600 \times 1000 = 15\,600\,000$ placas posibles. Nota cómo el número de opciones en cada etapa puede depender del número de la etapa, pero siempre es fijo para esa posición.

El principio aditivo: por qué "o" se convierte en "+"

Formalmente: si una tarea se puede realizar de $m$ maneras o de $n$ maneras, pero no de ambas simultáneamente (los casos son disjuntos, sin traslape), entonces el total de maneras es $m + n$ .

La diferencia con el principio multiplicativo es crucial: aquí los casos son mutuamente excluyentes — el objeto pertenece a una categoría u otra, jamás a ambas. Ejemplo: ¿cuántos enteros del 1 al 20 son múltiplos de 3 o múltiplos de 7? Los múltiplos de 3 en ese rango son $\{3,6,9,12,15,18\}$ : hay 6. Los múltiplos de 7 son $\{7,14\}$ : hay 2. Como ningún número del 1 al 20 es múltiplo de ambos ( $21$ es el primero), los casos son disjuntos: total $= 6 + 2 = 8$ .

Cada vez que el enunciado dice "elige A o elige B (excluyentes)", piensa en sumar. La palabra "o" en combinatoria suele señalar una adición, mientras que "y" suele señalar una multiplicación. Reconocer esta diferencia resuelve el 80 % de los problemas básicos.

Combinando ambos principios

Los problemas reales mezclan ambos principios. Considera: ¿cuántos números de 3 dígitos (del 100 al 999) son pares o tienen todos sus dígitos impares? Caso 1 (número par): el último dígito es par ( $0,2,4,6,8$ : 5 opciones), el primero puede ser $1$ – $9$ (9 opciones), el del medio $0$ – $9$ (10 opciones). Total caso 1: $9 \times 10 \times 5 = 450$ . Caso 2 (todos los dígitos impares): cada dígito es impar ( $1,3,5,7,9$ ). El primero tiene 5 opciones, el segundo 5, el tercero 5. Total caso 2: $5 \times 5 \times 5 = 125$ . Como los casos son disjuntos (un número par no puede tener todos los dígitos impares), el total es $450 + 125 = 575$ .

La estrategia es: identificar los casos disjuntos primero (suma), y dentro de cada caso aplicar el principio multiplicativo a las etapas independientes. Dibuja un árbol de decisiones si te ayuda a visualizar la estructura.

Problema tipo ONEM: ¿Cuántos números de 4 dígitos tienen exactamente un dígito igual a 5? Elegimos qué posición ocupa el 5 (4 formas). El dígito en esa posición es 5 (1 forma). Las otras 3 posiciones deben ser distintas de 5: la primera posición (si no es la del 5) tiene 8 opciones ( $1$ – $9$ sin el 5), y las otras dos tienen 9 opciones cada una ( $0$ – $9$ sin el 5). Pero hay que distinguir si la posición del 5 es la primera o no. Si el 5 está en la primera posición: $1 \times 9 \times 9 \times 9 = 729$ . Si el 5 está en otra posición (3 posibilidades): para cada una, la primera posición tiene 8 opciones, y las dos restantes 9 cada una: $3 \times 8 \times 9 \times 9 = 1944$ . Total: $729 + 1944 = 2673$ .

Problemas resueltos del capítulo

Problema 1 (nivel 1): Un menú tiene 3 entradas, 5 platos y 2 postres. ¿Cuántas comidas completas (una de cada categoría) se pueden armar? Solución: $3 \times 5 \times 2 = 30$ comidas.

Problema 2 (nivel 2): ¿Cuántos números de 3 dígitos distintos se pueden formar con los dígitos $\{1, 2, 3, 4, 5\}$ si no se puede repetir ningún dígito? Solución: primer dígito tiene 5 opciones, segundo 4 (quedan 4 sin usar), tercero 3. Total: $5 \times 4 \times 3 = 60$ .

Problema 3 (nivel 2, ONEM): ¿Cuántas cadenas de 5 bits (secuencias de 0s y 1s) tienen al menos un 1? Solución directa: $2^5 = 32$ cadenas en total, de las cuales solo 1 no tiene ningún 1 (la cadena 00000). Por complemento (que veremos en detalle en la lección 1.4): $32 - 1 = 31$ cadenas con al menos un 1. Aquí ya vemos que los principios se apoyan mutuamente.

Principio de adición y multiplicación