Módulo 2 - Separadores

Este es un pequeño tema de combinatoria que a veces se ve en entrenamientos, a veces se ve con un ejemplo, y a veces no se ve. El siguiente texto pretende ser un ligero apoyo al estudiante interesado en este "nuevo" tema sobre contar cosas. La idea detrás de esta forma de contar quizá sea rara a primera vista, pero ya a segunda vista no parece tan descabellada (y hasta podría llegar a ser intuitiva, pero es cuestión de que el estudiante relacione adecuadamente los conceptos básicos).

Bueno, empecemos. El tema se conoce informalmente como separadores, y este tema da lugar a otro conocido como combinaciones con repetición. En los entrenamientos en Ensenada trabajamos con los otros temas, a saber: permutaciones sin repetición, permutaciones con repetición, y combinaciones sin repetición. En aquel entonces no le dimos esos nombres, pero creo que a estas alturas ya podrías adivinar cuáles fórmulas son de qué tema (primer ejercicio para el lector: relacionar las fórmulas de los entrenamientos con los tres temas antes mencionados).

¿Por qué se llamam "separadores"? Buena pregunta. Pero para darle suspenso al asunto, dejaremos que el lector lo deduzca a través del siguiente ejemplo.

1. Un Ejemplo Ilustrativo: Discusión, Solución y Conclusiones

Usaremos el siguiente ejemplo para mostrar la utilidad de los separadores en algunos problemas de combinatoria.

Ejemplo.
¿Cuántas palabras de tres letras hay, tales que se pueden usar las letras del alfabeto \(\{a,b,c,d\}\) y que el orden de las letras no importa? Por ejemplo, las palabras aab, aba, baa son la misma palabra.

Análisis
Este parece el típico problema que poníamos hasta el cansancio en los primeros entrenamientos de combinatoria. Pero notamos algo: No podemos utilizar directamente las formulitas que aprendimos en aquellos tiempos (anda, inténtalo para que te convenzas).

Ante esta situación, tenemos que buscar otras maneras de atacar el problema. Siempre que veamos que algo no sale directamente con lo que sabemos, debemos intentar buscar formas de hacerlo parecer a algo que si sabemos y empezar a atacar. Vamos a usar esta técnica en la solución 2.

Por mientras, para una primera solución, vamos a irnos por las piedritas. Usaremos el camino de “los casitos”, en donde los casos serán: todas las letras iguales, dos letras iguales, y todas las letras distintas. Si contamos bien, habremos terminado correctamente el problema.

Solución 1 (Por casos)
Analicemos los casos:

• Caso 1) Todas las letras son iguales.
  En este caso, vemos que las palabras son 4: aaa, bbb, ccc, ddd.
• Caso 2) Dos letras son iguales, la tercera es distinta.
  Si la letra que se repite es la a, las posibilidades son: aab, aac, aad. Por cada letra tenemos una situación similar, así que deducimos que el total de palabras en este caso es 12.
• Caso 3) Las tres letras son distintas.
  Haciendo una búsqueda lexicográfica (como en los diccionarios), obtenemos las palabras: abc, abd, acd, bcd. En total son 4 palabras.

Entonces el total de palabras que pide el problema es \(4+12+4=20\). \(\square\)


Solución 2 (Por separadores)
Vamos a denotar por “O” a alguna de las cuatro letras de nuestro peculiar alfabeto. Como el orden no importa, en las palabras que buscamos podemos dejar las letras a hasta la izquierda, seguidas de las b, luego las c, y por último las d.

Nosotros queremos todas las palabras de la forma OOO, donde O como dijimos puede ser cualquiera de las cuatro letras. Pero haremos uso de separadores, que denotaremos por “ | ”. Tenemos 4 posibles letras, así que usaremos 3 separadores entre las letras O de la siguiente manera:

• Lo que quede a la izquierda del 1er separador serán a's.
• Lo que quede entre el 1er y 2do separador serán b's.
• Lo que quede entre el 2do y 3er separador serán c's.
• Y lo que quede a la derecha del 3er separador serán d's.

Con esta asignación, tenemos que:

• O | O | | O  representa la palabra abd.
• | O | O | O representa la palabra bcd.
• ¿Cómo representarías a la palabra aad?

Gracias a los separadores podemos asegurar que obtendremos todas las palabras buscadas (¿Por qué? Esta es una pregunta interesante, haz el esfuerzo por pensar en su respuesta), así que lo único que tenemos que hacer es contar ahora las palabras que tienen 3 O’s y 3 |’s, lo que ya sabemos hacer hasta con los ojos vendados:
\[ \binom{3+3}{3} = \binom{6}{3} = \frac{6!}{3! 3!} = 20 \]
Vemos que son 20 palabras, así que las dos soluciones coinciden. \(\square\).


Conclusiones
Si comparamos las dos soluciones, vemos que es más sencilla la primera solución. Sin embargo, tuvimos “suerte” de que sólo fueran palabras de 3 letras y que el alfabeto tenía 4 disponibles, pero si aumentamos en número de letras entraremos en más y más talacha (que, haciéndolo con paciencia y orden, saldrá eventualmente el resultado correcto).

A veces lo que se hace en matemáticas es intentar simplificar inteligentemente las cosas. En ocasiones no se podrá, y habremos que talachar un rato (¡Recuerda que hacer talacha no es el fin del mundo!). Pero hay otras ocasiones en las que al pensar un poco podemos encontrar bonitos atajos para acortar el camino.

Justo la idea de los separadores viene a eso: a simplificar las cuentas. La fuerza de los separadores se basa en dos cuestiones que se deben de observar con cuidado antes de usar esta técnica:

1. Estamos buscando combinaciones (escoger objetos sin importar el orden), PERO en estas combinaciones el mismo objeto puede volver a aparecer.
2. Como el orden no importa, justo podemos hablar de la 1ra categoría, la 2da categoría, etcétera, y a cada categoría delimitarla por los separadores.

Repito: Hay que usar los separadores con cuidado. Para reforzar un poco la idea de los separadores, se proponen a continuación unos cuantos problemas para que los razones y veas en dónde y cómo se pueden utilizar los separadores. Una vez hecho esto, intenta buscar una solución sin separadores para que compares las soluciones.

Espero que les haya gustado este tema. Ojalá recuerden los puntos clave y no tanto la fórmula importante (la cual viene en los siguientes problemas, el problema 6 de hecho).

2. Lista de Problemas

1. En una tienda dan 4 tipos de dulce. ¿De cuántas maneras se pueden comprar 10 dulces?

2. ¿De cuántas maneras se pueden servir 15 vasos de jugo, si se tienen los jugos de manzana, mango, piña, naranja y guanábana?

3. Encuentra el total de pares ordenados de enteros positivos \((x,y)\) tales que \(x+y=2012\).

4. Mismo problema que el anterior, pero ahora con \((x,y,z)\) tales que \(x+y+z=2012\).

5. Sea \(n\) un entero positivo. Encuentra el total de soluciones enteras positivas de
\[ x_1 + x_2 + \ldots + x_r = n. \]

6. Demuestra que el número de formas de escoger \(k\) objetos de un total de \(n\) objetos, en donde el orden no importa pero se pueden repetir objetos (combinaciones sin repetición), es igual a
\[ \binom{ n + k – 1 }{k} \]

7. Encuentra la cantidad de números naturales menores que 10, 000 cuyas cifras sumen 9.

8. (*) Mismo problema que el anterior, pero que la suma de las cifras sea 13.

9. (*) Encuentra el total de tripletas ordenadas \((x,y,z)\) de enteros no-negativos tales que \(x+y+z \leq 20\).

10. (*) Encuentra el total de cuartetas ordenadas de enteros \((a,b,c,d)\) tales que \(a+b+c+d=100\), y además que \(a \geq 30\), \(b > 21\), \(c \geq 1\), \(d \geq 1\).

Recompensa:

100 EXP incompleto,

500 EXP probs. 1-7,

1000 EXP probs. 1-10